分析合并排序的复杂性

Question

我写的代码如下：

def merge(A, B): #merging two sorted lists
   index_a = index_b = 0
   result = []
   while(index_a < len(A) and index_b < len(B)):
       if(A[index_a] <= B[index_b]):
           result += [A[index_a]]
           index_a += 1
       else:
           result += [B[index_b]]
           index_b += 1
   if(index_a != len(A)):#adds all remaining elements
       result += A[index_a:]
   elif(index_b != len(B)):
       result += B[index_b:]
   return result

def merge_sort(L):
   if(len(L) == 0 or len(L) == 1):
       return L
   else:
       a = merge_sort( L[:len(L)/2] )
       b = merge_sort( L[len(L)/2:] )
       return merge(a , b)

所以我可以理解 merge_sort 函数的复杂性，如上所示，是每个递归调用的 log(n)。我有点困惑的是在合并函数中所采取的步数，首先是两个分配，但之后我不知道如何获得最坏情况下所采取的步数，因为我想不出在哪里停止A或B及后面的加法。

任何帮助将不胜感激。谢谢。

Answer 1

您构建合并的方式虽然性能稍高，但让您更难看出复杂性。试试这个：

def merge(A, B): #merging two sorted lists
   index_a = index_b = 0
   result = []
   while(index_a < len(A) or index_b < len(B)): # NOTE OR
       if index_a < len(A) and (index_b == len(B) or A[index_a] <= B[index_b]): # NOTE EXTRA CONDITIONS
           result += [A[index_a]]
           index_a += 1
       else:
           result += [B[index_b]]
           index_b += 1
   return result

def merge_sort(L):
   ...

这里我用 while 循环条件的更改替换了 "then dump the rest" 代码（允许它运行直到两个输入列表都排序），以及 if 的额外条件-声明使它正常工作。如果您假设（正常情况下）连接两个数组的第二个数组的大小为 O(n)，则此修改不会改变算法复杂度。（即使你假设那是常数时间也没有改变，但解释起来稍微复杂一些。）

现在可以看到while循环的执行次数恰好等于列表长度的总和。这样就没有了"worst case".

分析合并排序的复杂性

Analysing merge sort complexity

python

big-o

mergesort

time-complexity