|
这几天在复习数据结构,顺便就对一些典型的海量数据的经典问题写一下自己的心得咯 一、第一个典型的问题就是，"在大量数据中（1千万以上）中,选出最大的k个数" ,有3种最快的方法,可以达到时间复杂度为O(n) 1、利用HASH方法保存数组中元素的出现次数，然后从大到小线性扫描，既可得到最大前k个数,时间复杂度为O(n+k),当k比较小时,可以忽略,则为O(n) 2、第二种方法是从瀚斌师兄那里得知的，方法很巧妙咯，利用的是快排的思想，快排的思想是:先选中轴(pivot),然后把数组分成2块,然后继续对那2块进行选中轴,然后分块,递归下去......因为我们只需要最大的K个数,所以在数组分开2块之后,我们没必要对2块都进行排序,只要对数子大的那块进行排序即可,因为那里有我们需要的最大k个数,即每次分裂,我们都会抛弃另一半,这样就加快了速度!这里的时间复杂度我算得的是O(n+Inn),约为O(n)咯 3、第三种方法是用最小堆，先取出一定的数据k用来建最小堆，然后读入记录，假如记录比树中最小的数(即堆顶元素)小，则直接抛弃，继续读下一条，否则就替换堆顶元素，总的时间复杂度为 建树时间+插入记录，因为建树的时候，k是常数，所以所用时间可以忽略，最坏的情况下,每次都要插入,且比较次数都为logk 则O( (n-k)*logk ),有因为m为常数,所以时间复杂度为0(n) 二、第二类问题是在大量数据中（1千万以上），文本数据，选出出现频率最高的前k条文本数据 因为是要找频率最高的，所以一定是要遍历数据的，这不可避免的，所以时间复杂度最快也就为0(n)咯,看到O(n)的时间复杂度,很容易就想到HASH方法了,而且要处理得数据是文本,用HASH是最好不过的了,至于怎么样HASH呢,可以用文本的长度,ASCII码的和作为HASH的参数,哈希表保存的是对应的记录的出现次数 HASH完后,然后找出哈希表中出现次数最大的前K个即可,可用上面讲的第一种方法 总的时间复杂度为O(n+m),m为哈希表中的数据项(m<=n),时间复杂度可看成O(n),因为常数通常是被忽略的 在求频率的问题上HASH方法是最常用的方法,这个一定要记住咯!HASH的时间复杂度通常为O(n) 另外在一些权重经常发生变化的数据中,采用堆排序是较好的方法,因为每次更新一条记录所用的时间也就堆的深度,即O(logn) 以上可能会有不对的地方咯,欢迎讨论^_^ |
|
|
