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

4

4 回答 4

12

这不是一个完整的答案。但是，如果列表已排序，那么您的问题在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
于 2012-06-19T02:59:52.980 回答
2

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

您的问题陈述表明您必须将数组缩减为单个元素，总共执行 n-1 次缩减操作。因此，所执行的归约操作的数量在 O(n) 的数量级上。为了实现 O(n) 的总体运行时间，每个归约操作必须在 O(1) 中运行。

您已经明确定义了归约操作：

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

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

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

这个答案本身并不能回答你的问题，但我相信它的相关性足以保证答案。

于 2012-06-19T01:32:52.753 回答
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>
于 2012-06-19T12:37:14.800 回答
0

O(nlogn) 很简单 - 只需使用堆、trap 或跳过列表。

O(n) 听起来很难。

https://en.wikipedia.org/wiki/Heap_%28data_structure%29
https://en.wikipedia.org/wiki/Treap
https://en.wikipedia.org/wiki/Skip_list
于 2012-06-26T03:56:55.450 回答