在O(n)时间内提取2个数字n次，并将它们相加后放回，而不是在O(n*log(n))时间内进行。

Question

在O(n)时间内提取2个数字n次，并将它们相加后放回，而不是在O(n*log(n))时间内进行。

arraysalgorithmlistmathdata-structures

23

我给大家介绍一个我教授在课堂上展示的问题，以及我的O(n*log(n))解决方案：

给定一个包含n个数字的列表，我们想要执行以下n-1次操作：

提取列表中最小的两个元素x和y，并展示它们
创建一个新数字z，其中z = x+y
将z放回到列表中

建议使用数据结构和算法来实现O(n*log(n))和O(n)：

解决方案：

我们将使用一个最小堆：

只需创建一次堆即可花费O(n)。之后，提取两个最小元素将花费O(log(n))，将z放入堆中将花费O(log(n))。

执行以上n-1次操作将花费O(n*log(n))，因为:

O(n)+O(n∙(logn+logn ))=O(n)+O(n∙logn )=O(n∙logn )

但如何以 O(n) 的时间复杂度完成？

编辑：

说“从列表中提取两个最小元素 x 和 y，呈现它们”，我是指 printf("%d,%d" , x,y)，其中 x 和 y 是当前列表中最小的元素。

- JAN

7

你不可能误解这个问题，对吧？ :) 我的第一反应是说这是不可能的。很明显，你需要遍历数组（n-1）次，这意味着你将执行某些操作，该操作的时间复杂度为O(n)。要实现总体的O(n)时间复杂度，你需要使该操作的时间复杂度为O(1)。在已排序的列表中，可以在O(1)时间内找到两个最小值，但是将一个值重新插入列表并保持排序则需要log(n)时间。除非你想使用基数排序，但那有点靠不住。 - cheeken

对于这个问题，我还是很好奇的。+1 :) - cheeken

8

鸡的下意识反应的证明：假设你可以这样做。进一步假设，当你将 z 插入列表时，你在其上贴一个标记，表示“这是一个计算出来的值，而不是原始值”。最后，假设当你呈现数字时，只打印出未设置标记的数字。然后，您已经在 O(n) 时间内对数字列表进行了排序。因此，需要某种欺骗手段，例如对固定大小整数执行基数排序。 - Steve Jessop

@SteveJessop 啊，非常好的推理。 - cheeken

@hatchet：不，我在15分钟前给他发送了一封电子邮件。我希望他很快会回复，然后我会在这里发布他的答案。 - JAN

显示剩余11条评论

4个回答

2

在一般情况下，这是不可能的。

你的问题陈述表明你必须将数组减少到一个元素，执行n-1个减少操作。因此，执行的减少操作数量大约为O(n)。为了实现O(n)的整体运行时间，每个减少操作必须在O(1)内运行。

你已经清楚地定义了你的减少操作：

- 删除数组中的2个最小元素并打印它们，然后 - 将这些元素的总和插入数组中。

如果你的数据结构是排序列表，那么在O(1)时间内删除两个最小元素是微不足道的（从列表的末尾弹出它们）。然而，在O(1)内重新插入元素是不可能的（在一般情况下）。正如SteveJessop指出的那样，如果你能在O(1)时间内插入到一个排序列表中，那么所得到的操作将构成一个O(n)的排序算法。但是并没有这样已知的算法。

这里有一些例外情况。如果你的数字是整数，你可以使用“基数插入”来实现O(1)插入。如果你的数字数组在数字线上足够稀疏，你可以在O(1)时间内推断出插入点。还有许多其他例外情况，但它们都是例外。

这个答案并没有直接回答你的问题，但我认为它足够相关，值得一提。

- cheeken

这实际上只是我和其他人评论的转载。但考虑到似乎没有解决方案，我认为将其发布为答案是明智的。 - cheeken

但即使使用基数排序，时间复杂度也是O(n+m)，其中m是桶的数量（基数？桶排序等同于基数排序，但我不知道正确的术语），m>=n，因为您不知道哪些桶中有数据（必须尝试所有桶，即使它们为空）。而且，这还假设没有负数。如果需要重新检查旧桶，则时间复杂度为O(n+m^2)。 - acattle

请看我的回答，如果数组被替换为链表，则重新插入的时间复杂度为O(1)是可行的。然而，仍然存在一个隐含的排序在后台潜伏。 - btilly

1

如果值的范围小于n，则可以在O(n)时间内解决。

1> 创建一个大小等于值范围的数组mk，并将其初始化为零

2> 遍历数组并增加数组元素位置处的mk值。即，如果数组元素是a[i]，则增加mk[a[i]]

3）在进行n-1次操作后，按以下步骤呈现答案：

有两种情况：

情况1：所有a[i]都是正数

        traverse through mk array from 0 to its size
        cnt = 0
        do this till cnt doesn't equal 2
          grab a nonzero element decrease its value by 1 and increment cnt by 1
        you can get two minimum values in this way
        present them 
        now do mk[sum of two minimum]++

情况2：a [i] 中的一些数是负数

        <still to update>

- amitkarmakar

0

O(nlogn)很容易 - 只需使用堆、treap或skiplist。

O(n)听起来很难。

https://en.wikipedia.org/wiki/Heap_%28data_structure%29
https://en.wikipedia.org/wiki/Treap
https://en.wikipedia.org/wiki/Skip_list

- user1277476

用伸展树可能会非常快，但仍然可能是O(nlogn)。伸展树的好处在于最近使用的节点会被移动到树的顶部附近。 - user1277476

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- btilly · Accepted Answer

这不是一个完整的答案。但如果列表已排序，则您的问题可以很容易地在O(n)时间内完成。为此，请将所有数字排列成链接列表。维护一个指向头部和中间某个位置的指针。在每一步中，从头部取出前两个元素，打印它们，将中间指针推进到应该放置总和的位置，并插入总和。

起始指针将移动接近2n次，中间指针将移动约n次，进行n次插入。所有这些操作都是O(1)，因此总和为O(n)。

通常情况下，您无法以时间O(n)排序，但有许多特殊情况可以做到。因此，在某些情况下是可行的。

当然，一般情况下不能在时间O(n)内解决。为什么呢？因为根据您的输出，您可以在时间O(n)内运行程序的输出，按顺序构建成对求和的列表，并将它们过滤出输出。剩下的就是原始列表中的元素按顺序排列。这将得到一个O(n)的常规排序算法。

更新： 我被要求展示如何从输出(10, 11), (12, 13), (14, 15), (21, 25), (29, 46)到输入列表？诀窍是始终保持一切有序，然后您就知道如何查找。对于正整数，下一个即将使用的总和始终位于该列表的开头。

Step 0: Start
  input_list: (empty)
  upcoming sums: (empty)

Step 1: Grab output (10, 11)
  input_list: 10, 11
  upcoming_sums: 21

Step 2: Grab output (12, 13)
  input_list: 10, 11, 12, 13
  upcoming_sums: 21, 25

Step 3: Grab output (14, 15)
  input_list: 10, 11, 12, 13, 14, 15
  upcoming_sums: 21, 25, 29

Step 4: Grab output (21, 25)
  input_list: 10, 11, 12, 13, 14, 15
  upcoming_sum: 29, 46

Step 5: Grab output (29, 46)
  input_list: 10, 11, 12, 13, 14, 15
  upcoming_sum: 75