好好回答一下吧。首先對於1億的資料量，要求不高的話，大可只使用一個最小堆來維護前10萬個最大的數。不妨設數的總數為N，需要選出的數為M，那麼這種方法帶來的時間複雜度為：這個方法最大的缺點是沒有平行計算。如果比1億資料量再大，比如到100億這個量級，那麼就需要使用平行計算了，下面我詳細說一下我的思路。1) 首先將這些資料隨機分成K堆，不妨假設正好平均分配，時間複雜度為。2) 使用K個任務並行的選出每一堆的前M大的數，這一步的時間複雜度為，此時生成了K組長度為M的有序序列。3) 使用多路歸併排序選出這K組序列的前M大的數，這一步的時間複雜度為因此假設第2步並行完成，那麼總體的時間複雜度就是。至此演算法得到了常數級別的最佳化。但是還沒完，注意到2)中每個序列都選了前M大的數，這個是可以繼續改進的。我們可以想象一種場景：2個桶裡總共有10個球，球是隨機分佈的，規定一種操作可以從這2個桶裡拿至多L個球，這時我們怎麼確定這個L使得我們能夠以一個我們能接受的機率拿到所有的球？顯然當L=10的時候，我們當然可以100%的拿到這全部球，但是開銷太大了。由於球是隨機分佈的，可以知道10個球全部落入落入一個盒子裡的機率非常的小，是。因此我們可以先把這種請噹噹成一箇中彩票的事件，先不管他，直接把L設成9。既然我們犧牲了一部分可靠性降低了開銷，那麼為什麼不能把L設的在低一點？究竟應該設多低？這其實是另外的一個問題了，我認為為了解決這個問題不應該從L入手，而是我們設定一個最低能接受的可靠性機率P，找到最小的L滿足我們要求的P即可。因此我們可以使用如上方法最佳化2)。設我們要求的最低可靠性為P, 最佳化函式為2) 使用K個任務並行的選出每一堆的前大的數，這一步的時間複雜度為, 此時生成了K組長度為的有序序列。我可以給出一個數, 可以看出這個函式的威力。所以用這種方法，可以在實際中獲得很多倍的速度提升。但是必須解決的問題是可靠性問題，但這個問題其實很好辦，只需要驗證一下在3)時有沒有把一個序列用盡，如果用盡了並且最後一個數不是這個序列裡的最後一個數，那麼說明這個序列的第個數也可能出現在最壞的結果。那麼最簡單的做法就是再從這個序列中補上一部分資料，使得最後的答案時正確的。所以這時我們得到了一個以P為成功率的演算法，這個演算法可能比未最佳化前快好多倍，但是有(1-P)的中獎機率。欣慰的是我們可以判斷中沒中獎，再不濟就是拋棄這次的結果再跑一次未最佳化前的演算法唄。