logo标签列表

解决k分区变体问题的算法

algorithm
3

我的算法设计课作业中出现了这个脑筋急转弯：

Given a list of N distinct positive integers, partition the list into two 
sublists of n/2 size such that the difference between sums of the sublists 
is maximized.
Assume that n is even and determine the time complexity.

乍一看，解决方案似乎是

  1. 通过归并排序对列表进行排序
  2. 选择n/2位置
  3. 对于所有大于该位置的元素，添加到高数组中
  4. 对于所有小于该位置的元素，添加到低数组中

这将具有时间复杂度O((n log n)+ n)

是否有更好的算法选择来解决这个问题？

时间复杂度降至O(nlogn)。 - calebds
2个回答
8

由于您可以在O(n)时间内计算中位数，因此您也可以在O(n)时间内解决此问题。计算中位数，并将其用作阈值，创建高数组和低数组。

请参见http://en.wikipedia.org/wiki/Median_search有关在O(n)时间内计算中位数的信息。

4
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接