分析マージソートの複雑

Question

は、私が書いたコードは次のとおりです。上図の各再帰呼び出しのログ（n）があるよう

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機能の複雑さを理解することができます。私が少し混乱していたのは、マージ関数のステップ数、最初は2つの割り当てでしたが、その後は最悪の場合に取られるステップ数を取得する方法がわかりません。 AまたはBおよび後の追加。

本当にありがとうございます。ありがとうございました。

Answer 1

あなたのマージを構成した方法は、やや性能が向上しますが、その複雑さを見るのが難しくなります。私は（両方の入力リストがソートされるまで、それが実行できるようにする）whileループ条件を変更して、「その後、残りをダンプする」コード、および追加の条件に取って代わってきました。ここ

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): 
    ... 

：これを試してみてくださいその文を正しく動作させるためのif文。 2つの配列を連結することが2番目の配列のサイズでO（n）であると仮定すれば、アルゴリズムの複雑さはこの変更によって変更されません。 （一定の時間だと仮定しても変わらないが、説明するのは少し複雑だ）

ここで、whileループの実行回数は、リスト。こうして「最悪の場合」はありません。