元件总结我有两个阵列：算法在未排序的阵列
对于每个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，谢谢，明白了。 –