Analyzing Mergesort Komplexität

Question

Der Code I schrieb wie folgt:

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) 

So kann ich die Komplexität der merge_sort Funktion verstehen, wie oben gezeigt, ist log (n) für jeden rekursiven Aufruf. Was ich ein wenig verwirrt war, ist in der Zusammenführungsfunktion die Anzahl der durchgeführten Schritte, zuerst die zwei Aufgaben, aber danach weiß ich nicht, wie ich die Anzahl der Schritte im schlimmsten Fall erreichen kann, weil ich nicht weiß, wo ich in der Länge anhalten soll A oder B und die spätere Zugabe.

Jede Hilfe würde wirklich geschätzt werden. Danke.

Answer 1

Die Art und Weise, wie Sie Ihre Zusammenführung strukturiert haben, ist zwar etwas performanter, macht es jedoch schwieriger, die Komplexität zu erkennen. Versuchen Sie folgendes:

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

Hier habe ich den „dann wirft den Rest“ Code mit einer Änderung der while-Schleife Bedingung ersetzt (so dass es laufen, bis beide Eingangslisten sortiert sind) und eine zusätzliche Bedingung zu die if-Anweisung, damit das funktioniert. Wenn Sie annehmen, dass (wie es normal ist) die Verkettung zweier Arrays O (n) in der Größe des zweiten Arrays ist, ist die algorithmische Komplexität durch diese Modifikation unverändert. (Es ist unverändert, auch wenn Sie davon ausgehen, dass das konstante Zeit ist, aber es ist etwas komplizierter zu erklären.)

Jetzt können Sie sehen, dass die Anzahl der Wiederholungen der While-Schleife genau gleich der Summe der Länge von ist die Listen. Auf diese Weise gibt es keinen "schlimmsten Fall".