arrays - 提取 2 个数字 n 次并将加法放回 O(n) 而不是 O(n*log(n))

Question

我正在用我的 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 是当前列表中的最小元素。

Answer 1

这不是一个完整的答案。但是，如果列表已排序，那么您的问题很容易在 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