提取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