本文共 738 字,大约阅读时间需要 2 分钟。
们要找的Top10了。
不难分析出,这样,算法的最坏时间复杂度是N*K, 其中K是指top多少。
算法三:堆
在算法二中,我们已经将时间复杂度由NlogN优化到N*K,不得不说这是一个比较大的改进了,可是有没有更好的办法呢?
分析一下,在算法二中,每次比较完成之后,需要的操作复杂度都是K,因为要把元素插入到一个线性表之中,而且采用的是顺序比较。这里我们注意一下,该数组是有序的,一次我们每次查找的时候可以采用二分的方法查找,这样操作的复杂度就降到了logK,可是,随之而来的问题就是数据移动,因为移动数据次数增多了。不过,这个算法还是比算法二有了改进。
基于以上的分析,我们想想,有没有一种既能快速查找,又能快速移动元素的数据结构呢?
回答是肯定的,那就是堆。
借助堆结构,我们可以在log量级的时间内查找和调整/移动。因此到这里,我们的算法可以改进为这样,维护一个K(该题目中是10)大小的小根堆,然后遍历300万的Query,分别和根元素进行对比。
思想与上述算法二一致,只是在算法三,我们采用了最小堆这种数据结构代替数组,把查找目标元素的时间复杂度有O(K)降到了O(logK)。
那么这样,采用堆数据结构,算法三,最终的时间复杂度就降到了N*logK,和算法二相比,又有了比较大的改进。
总结:
至此,算法就完全结束了,经过上述第一步、先用Hash表统计每个Query出现的次数,O(N);然后第二步、采用堆数据结构找出Top10,N*O(logK)。所以,我们最终的时间复杂度是:O(N) +N'*O(logK)。(N为1000万,N’为300万)。
转自与:http://blog.sina.com.cn/s/blog_4a80dbb00101ealh.html
转载地址:http://estii.baihongyu.com/