Wiederholung für rekursive Einfügesortierung

9

Ich habe dieses Problem mit CLRS versucht (Seite 39, 2.3-4).

Wir können die Einfügesortierung als rekursive Prozedur wie folgt ausdrücken. Zum Sortieren sortieren A[1... n]wir rekursiv A[1... n-1]und fügen es dann A[n]in das sortierte Array ein A[1... n-1]. Schreiben Sie eine Wiederholung für die Laufzeit dieser rekursiven Version der Einfügesortierung.

Die Wiederholung, die ich bildete, war

T.(n)={Θ(1)wenn n=1,T.(n- -1)+Θ(n)wenn n>1.

Meine Argumentation

  • der Basisfall von n=1 Die Liste ist so sortiert, dass es keine Arbeit gibt, daher konstante Zeit.
  • In allen anderen Fällen hängt die Zeit davon ab, A[1...n-1]ob die Sequenz sortiert und dann in diese Sequenz eingefügt wird. Daher sollte es ihre Summe sein, dhT.(n- -1)+Θ(n).

Ich wollte wissen, ob die Wiederholungsbeziehung korrekt ist. Wenn nicht, was sind die Fehler und wie kann eine Wiederholungsbeziehung richtig formuliert werden?

Aseem Bansal
quelle
1
Sie könnten an unseren Referenzfragen interessiert sein . Insbesondere ist der Begriff "Laufzeit" unscharf, die Wiederholung mitΘ-terms ist nicht die schönste Art, Dinge zu formulieren, und verschiedene Arten der Lösung von Rezidiven wurden diskutiert. Beachten Sie, dass "Ja-Nein" -Fragen hier im Allgemeinen unerwünscht sind. (Ich stelle fest, dass die Frage alt ist; hinterlasse den Kommentar als Referenz.)
Raphael

Antworten:

6

Gemäß der von Ihnen angegebenen Beschreibung ist die Wiederholung korrekt.
Sie könnten denken, es sollte
T (n) = sein

{1, n=1T.(n- -1) + Θ(lÖG n), Ötherwichse}}

Da Sie die Einfügestelle mithilfe der Binärsuche finden können, müssen Sie im schlimmsten Fall alle Elemente entfernen, um das Element tatsächlich einzufügen.
hcf
quelle
Das lineare Suchen dauert O(n)und durch binäre Suche ist es O(log n). Aber ist nicht der schlimmste Fall die Bewegung aller Elemente, die erforderlich sind, O(n)um die Gesamtkomplexität zu erhöhen O(n)? Warum ist der Begriff in n != 1also O(log n)statt zu sein O(n)?
Aseem Bansal
2
du hast recht, genau das habe ich gesagt. Die obige Formel ist genau deshalb falsch, weil die Bewegung der Elemente O (n)
hcf
Ich sollte genauer lesen. Danke für die Antwort.
Aseem Bansal