Ich mache die Übungen in Einführung in den Algorithmus von CLRS. Dies ist keine benotete Hausaufgabe oder irgendetwas, ich versuche nur, das Problem zu verstehen.
Das Problem ist wie folgt:
Wir können die Einfügesortierung als rekursive Prozedur wie folgt ausdrücken. Im Um A [1..n] zu sortieren, sortieren wir rekursiv A [1..n-1] und dann fügen Sie A [n] in das sortierte Array A [1..n-1] ein. Schreib ein Wiederholung für die Laufzeit dieser rekursiven Version der Insertion Sortieren.
Die Lösung des Problems:
Da es im schlimmsten Fall O (n) Zeit braucht, um A [n] in die Sortiertes Array A [1. .n -1], erhalten wir die Wiederholung T (n) = O (1) wenn n = 1 , T (n-1) + O (n) falls n & gt; 1. Die Lösung für diese Wiederholung ist T (n) = O (n ^ 2).
Also verstehe ich, wenn n = 1 ist, dann ist es schon sortiert, also dauert es O (1) mal. Aber ich verstehe den zweiten Teil der Wiederholung nicht: Der O (n) -Teil ist der Schritt, in dem wir das Element, das sortiert wird, in das Array einfügen, das die Worst-Case-O (n) -Zeit einnimmt - der Fall, in dem wir das gesamte Array durchlaufen und an dessen Ende einfügen müssen.
Ich habe Probleme, den rekursiven Teil davon zu verstehen (T (n-1)). Bedeutet T (n-1), dass wir bei jedem rekursiven Aufruf ein Element weniger als ein Element des Arrays sortieren? Das scheint nicht richtig zu sein.
Ja, es folgt aus:
Um A [1..n] zu sortieren, sortieren wir rekursiv A [1..n-1] und dann füge A [n] in das sortierte Array A [1..n-1]
ein
Der "rekursiv sortierte A [1..n-1]" -Teil benötigt T (n-1) -Zeit (das ist einfach: wir definieren T (n) "the" Zeit, die es braucht, um n Elemente zu sortieren ", so ist die Zeit, die es braucht, um n-1 Elemente zu sortieren, trivialerweise T (n-1)), während die" A [n] in die sortierte Anordnung A [1..n-1 ] Teil nimmt (schlimmsten Fall) O (n) Zeit. Fügen Sie sie zusammen, um
zu erhaltenT (n) = T (n-1) + O (n)
Ich werde erklären, was ich mit dem Python-Code für Insertion sort unter Verwendung der Rekursion wie folgt verstehe:
def Einfügung_sort_r (A, n)
%Vor%Die für jeden Schritt benötigte Zeit wird durch die "c" -Werte während und die Anzahl der durchgeführten Schritte angezeigt. Wir stellen die Zeit dar, die für das Sortieren von (n-1) -Elementen in dem Schritt "insert_sort_r (A, n-1)" als T (n-1) benötigt wird, weil wir nicht genau wissen, wie dieser Wert in Bezug auf n sein wird. Dies ist die Idee der Rekursion. Um die Gleichung für den Fall darzustellen, wenn der Wert n ist, und für den Fall, dass der Wert (n-1) ist.
Tags und Links algorithm recursion sorting recurrence