合并排序合并运行时间anaylsis

我对合并排序中的合并函数的运行时分析存在一些混淆。合并排序合并运行时间anaylsis

Merg(A,p,q,r) 
1 n1=q-p+1 
2 n2=r-q 
3 let L[1..n1+1] and R[1..n2+1] be new arrays 
4 for i=1 to n1 
5  L[i] = A[p+i-1] 
6 for j =1 to n2 
7 R[j] = A[q+j] 
8 L[n1+1] = infinity 
9 R[n2+1] = infinity 
10 i =0 
11 j=0 
12 for k=p to r 
13 if L[i]<=R[j] 
14  A[k]=L[i] 
15  i=i+1 
16 else A[k] = R[j] 
17  j=j+1

在我的书，它说以下内容：看到，合并过程运行在O（n）的时间，其中n = R-P + 1，观察到每个线1-3和8-11的需要一定的时间，第4-7行的for循环占用O（n1 + n2）= O（n）时间，并且对于第12-17行的循环有n次迭代，每次迭代需要恒定的时间

我的问题是为什么第12-17行每次迭代需要不变的时间，并且不会影响运行时间，但是第4至7行的不需要一定的时间。对我来说，似乎两个循环都在做同样的事情。有人可以帮我澄清一下吗？谢谢！

来源

2011-10-05 Wonger

这是令人困惑的写。两个循环（4-7和12-17）具有相同的长度（n），并且两个循环的内部都是恒定时间（没有嵌套循环）。所以它们都是O（n），对于整个例程总共为O（n）。

关于杰瑞的回答，第4-7行很重要，因为他们仍然是O（n）。如果你可以神奇地删除12-17行，你仍然会有一个O（n）例程。

来源

2011-10-05 22:23:16

OH WOW。 IM哑巴哈哈。出于某种原因，我想他们是嵌套的，这会使它成为O（n^2），但它确实是2n，它只是O（n）。书的解释绝对不是以最好的方式写的，但我现在明白了。谢谢！ – Wonger

第1到第9行只是将输入（A）分成两部分（L和R）。第10行和第11行正在进行一些初始化以准备合并。合并本身来自12-17行。

督察，第12行（或者可以说，而不是它真正的问题）无关分析合并因为没有它确实是合并的一部分，在众人面前的一切。编辑：然而，最终，从1到27的单次迭代是线性的：在第4-7行中，您只需走过一次输入数组，将每个输入精确地分配给L或R.在第12行中， 27，然后你通过这两个部分，并将其复制回原始输入。忽略其他一些小的细节，如初始化i和j，操作的总数恰好是2N。对于大O符号，常数因子被忽略，所以它是O（N）。

来源

2011-10-05 22:21:33

那么，这也是我会承担的，但书中说，O（n）运行时间来自4-7行，而不是12-27行 – Wonger

合并排序合并运行时间anaylsis

回答

相关问题