元件總結我有兩個陣列：算法在未排序的陣列
對於每個b我，我要計算的最大b總和i的陣列A.例如元素，如果
然後我想要的2，3，4，6，和7最大元素之和在甲：
我知道如何計算總和b個我爲O最大元素（Ñ）時間，所以可以很容易地寫出用於在O（NK）時間運行整個任務的算法;但我需要運行在O（n log k）時間的算法。
所以，我怎麼能做到這一點的O（ñ日誌ķ）的時間？
基本上，您想要查找第一個數組中的k個最大元素。
這是該算法的草圖。你走過第一個數組。將元素插入到數據結構中 - 比方說一個B樹。插入到數據結構中的是log（k），因爲數據結構結構僅限於k個元素。因此，對於第k + 1條記錄，插入有點不同，因爲較大的值會覆蓋較小的值。 （比B樹有更好的數據結構，比如堆，但是你可能更熟悉一棵樹。）
在任何情況下，插入到這個數據結構中都是log（k）。您可以在O（n * log（k））操作中創建它。然後，你只需要讀取數據結構，即k。因爲它不會造成複雜性。所以，這就是你將如何構建這樣的算法。
有沒有辦法做到這一點在O（nlogk）時間而不使用其他數據結構？我得到了暗示，從數組B中的中間元素開始。 – Baekyeon
@Bekekon。 。 。我想你會從最大的元素開始，因爲其餘的都是該解決方案的子集。 –
我不擅長編寫完整的算法。我會嘗試使用您的例子來說明我的想法：
開始（4），我們發現10 + 15 + 11 + 20 = 56，以及分裂的進入
[10,15,11,20] [5,3,9,8,4,7,1,6]
和B的中間元素B分割成
[2,3] [6,7]
遞歸，我們有兩個減少總結的問題：
Q1: A' = [10,15,11,20] B' = [2,3]
Q2: A' = [5,3,9,8,4,7,1,6] B' = [6-4, 7-4]
取中間元素Q1和Q2的B'，分別處理Q1和Q2的A'。所有A'子問題中訪問的元素總數仍然是O（n），並且我們繼續將問題分解爲更小的子問題，直到log（k）次。
可能有一些操作來總結O（k）中的值。由於（如問題中所定義的），與O（n log k）時間複雜度相比，該O（k）可能被忽略。
@ AD.Net。 。 。因爲O（n log k）更快，而且通常是可取的。 –
@GordonLinoff，謝謝，明白了。 –