合并排序合并运行时分析
我对merge排序中的merge函数的运行时分析有些困惑。
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行的for oop有n次迭代，每一次迭代都需要恒定的时间
我的问题是，为什么第12-17行在每次迭代中占用固定的时间，而不影响运行时间，而第4-7行不占用固定的时间。在我看来，这两个循环似乎都在做同样的事情。有人能帮我澄清一下吗？谢谢!
回答 2
Stack Overflow用户
发布于 2011-10-06 06:23:16
它写得令人困惑。两个环路(4-7和12-17)具有相同的长度(n)，并且两个环路的内部是恒定的时间(没有嵌套环路)。所以它们每个都是O(n)，对于整个例程来说，总共是O(n)。
关于曾傑瑞的回答，4-7行很重要，因为它们仍然是O(n)。如果你能神奇地删除第12-17行，你仍然会有一个O(n)例程。
Stack Overflow用户
发布于 2011-10-06 06:21:33
第1到9行只是将输入(A)分成两部分(L和R)。第10行和第11行正在进行一些初始化，以便为合并做好准备。合并本身来自第12-17行。
实际上，第12行(或者可以说是第10行)之前的所有内容都与分析合并无关，因为它们根本就不是合并的一部分。
编辑:然而，最终，从1到27的单个迭代是线性的:在第4-7行中，您只遍历一次输入数组，将每个输入恰好分配给L或R一次。在第12-27行中，然后遍历这两部分，并将它们复制回原始输入。忽略其他一些次要的细节，比如初始化i和j，操作的总数正好是2N。对于大O表示法，常量因子被忽略，因此它是O(N)。
https://stackoverflow.com/questions/7668392
复制相似问题
腾讯云开发者
