Wie die algorithmische Raum Komplexität berechnen

Question

i bin die Überprüfung meiner Datenstrukturen und Algorithmen Analyse Lektion, und i eine Frage bekommen, dass, wie in den Raum Komplexität von Mergesort und schnell sortieren Algorithmen?

  

Die Tiefe der Rekursion ist nur O (LGN) für verkettete Liste merge-sort

     

Die Menge des zusätzlichen Stauraum für angrenzende Schnellsortierung erforderlich ist O (n).

Meine Gedanken:

Die beiden arbeiten beide Teile-und-Herrsche-Strategie, so dass ich denke, die Raum Komplexität der verketteten Liste Mergesort sollte als zusammenhängende schnelle gleich sein sort.Actually i opt für O (LGN), da vor jeder Iteration oder Rekursion Anruf, die Liste wird geteilt Hälfte.

Danke für alle Hinweise.

Answer 1

Der schlimmste Fall für die Tiefe der Rekursion quicksort nicht (notwendigerweise) O (log n), weil quicksort die Daten nicht teilen „in die Hälfte“, es spaltet es um einen Drehpunkt, der nicht der Median sein kann oder nicht. Es ist möglich, quicksort implementieren diese [*] anzusprechen, aber vermutlich die O (n) Analyse war eine grundlegende rekursiven quicksort Implementierung, nicht eine verbesserte Version. Das würde erklären die Diskrepanz zwischen dem, was Sie in der Blockquote sagen, und dem, was Sie sagen, sie unter „meine Gedanken“.

Anders als das Ich denke, Ihre Analyse ist Klang -. Weder Algorithmus verwendet keine zusätzlichen Speicher andere als einen festen Betrag pro Level der Rekursion, so Rekursionstiefen diktiert die Antwort

Eine andere Möglichkeit zur Rechenschaft für die Diskrepanz, nehme ich an, ist, dass die O (n) Analyse ist einfach falsch. Oder: „zusammenhängender quicksort“ ist kein Begriff, den ich zuvor gehört habe, also wenn es bedeutet nicht, was ich denke, es tut ( „quicksorting ein Array“), könnte es eine quicksort impliziert, dass unbedingt platz ineffizient ist in gewissem Sinne , wie beispielsweise eine zugeordnete Array anstelle des Sortierens in-place zurückkehrt. Aber es wäre albern quicksort und mergesort auf der Grundlage der Tiefe der Rekursion der mergesort gegen die Größe einer Kopie des Eingangs für den quicksort zu vergleichen.

[*] Insbesondere stattdessen die Funktion rekursiv auf beiden Teilen des Aufrufs, setzen Sie es in einer Schleife. Machen Sie einen rekursiven Aufruf auf dem kleineren Teil, und Schleife um den größeren Teil zu tun, oder äquivalent schieben (Zeiger auf) den größeren Teil auf einen Stapel von Arbeit später zu tun, und Schleife um den kleineren Teil zu tun. So oder so, stellen Sie sicher, dass die Tiefe des Stapels nie überschreitet log n, weil jedes Stück Arbeit nicht gesetzt auf dem Stapel ist höchstens halb so groß wie der Brocken, bevor es bis zu einer festgelegten Mindest (1 oder 2, wenn Sie rein mit quicksort Sortierung).

Answer 2

Ich bin nicht wirklich vertraut mit dem Begriff „zusammenhängenden quicksort“. Aber quicksort können haben entweder O (n) oder O (log n) Speicherkomplexität je nachdem, wie es umgesetzt wird.

Wenn sie umgesetzt wird, wie folgt:

quicksort(start,stop) {
    m=partition(start,stop);
    quicksort(start,m-1);
    quicksort(m+1,stop);
}

Dann wird der Raum Komplexität ist O (n) , nicht O (log n), wie allgemein angenommen wird. Dies liegt daran, Sie auf den Stapel zweimal auf jeder Ebene drängen, so dass der Raum Komplexität der zu Wiederholungen bestimmt:

T(n) = 2*T(n/2)

die Partitionierung Unter der Annahme, teilt die Anordnung in 2 gleiche Teile (best case). Die Lösung dieses Problems nach dem Master-Theorem T (n) = O (n).

Wenn wir die zweite quicksort Anruf mit Endrekursion im Code ersetzen Snippet oben, dann bekommen Sie T (n) = T (n / 2) und somit T (n) = O (log n) (von Fall 2 das Master-Theorem).

Vielleicht ist die "contiguous quicksort" bezieht sich auf die erste Implementierung, da die beiden Anrufe quicksort nebeneinander liegen, in welchem ??Fall der Raum Komplexität O (n) .