這幾天在復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu),順便就對一些典型的海量數(shù)據(jù)的經(jīng)典問題寫一下自己的心得咯

   一、第一個典型的問題就是，"在大量數(shù)據(jù)中（1千萬以上）中,選出最大的k個數(shù)" ,有3種最快的方法,可以達到時間復(fù)雜度為O(n)

          1、利用HASH方法保存數(shù)組中元素的出現(xiàn)次數(shù)，然后從大到小線性掃描，既可得到最大前k個數(shù),時間復(fù)雜度為O(n+k),當k比較小時,可以忽略,則為O(n)

           2、第二種方法是從瀚斌師兄那里得知的，方法很巧妙咯，利用的是快排的思想，快排的思想是:先選中軸(pivot),然后把數(shù)組分成2塊,然后繼續(xù)對那2塊進行選中軸,然后分塊,遞歸下去......因為我們只需要最大的K個數(shù),所以在數(shù)組分開2塊之后,我們沒必要對2塊都進行排序,只要對數(shù)子大的那塊進行排序即可,因為那里有我們需要的最大k個數(shù),即每次分裂,我們都會拋棄另一半,這樣就加快了速度!這里的時間復(fù)雜度我算得的是O(n+Inn),約為O(n)咯

          3、第三種方法是用最小堆，先取出一定的數(shù)據(jù)k用來建最小堆，然后讀入記錄，假如記錄比樹中最小的數(shù)(即堆頂元素)小，則直接拋棄，繼續(xù)讀下一條，否則就替換堆頂元素，總的時間復(fù)雜度為 建樹時間+插入記錄，因為建樹的時候，k是常數(shù)，所以所用時間可以忽略，最壞的情況下,每次都要插入,且比較次數(shù)都為logk 則O( (n-k)*logk ),有因為m為常數(shù),所以時間復(fù)雜度為0(n)

   二、第二類問題是在大量數(shù)據(jù)中（1千萬以上），文本數(shù)據(jù)，選出出現(xiàn)頻率最高的前k條文本數(shù)據(jù)

          因為是要找頻率最高的，所以一定是要遍歷數(shù)據(jù)的，這不可避免的，所以時間復(fù)雜度最快也就為0(n)咯,看到O(n)的時間復(fù)雜度,很容易就想到HASH方法了,而且要處理得數(shù)據(jù)是文本,用HASH是最好不過的了,至于怎么樣HASH呢,可以用文本的長度,ASCII碼的和作為HASH的參數(shù),哈希表保存的是對應(yīng)的記錄的出現(xiàn)次數(shù)

          HASH完后,然后找出哈希表中出現(xiàn)次數(shù)最大的前K個即可,可用上面講的第一種方法

          總的時間復(fù)雜度為O(n+m),m為哈希表中的數(shù)據(jù)項(m<=n),時間復(fù)雜度可看成O(n),因為常數(shù)通常是被忽略的

          在求頻率的問題上HASH方法是最常用的方法,這個一定要記住咯!HASH的時間復(fù)雜度通常為O(n)

另外在一些權(quán)重經(jīng)常發(fā)生變化的數(shù)據(jù)中,采用堆排序是較好的方法,因為每次更新一條記錄所用的時間也就堆的深度,即O(logn)

以上可能會有不對的地方咯,歡迎討論^_^