Wiederholung für rekursive Einfügesortierung

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) = {\begin{cases} Θ (1) & wenn n = 1, \\ T. (n - - 1) + Θ (n) & wenn n > 1. \end{cases}

$T(n) = \begin{cases}\Theta(1) & \textrm{if } n = 1,\\ T(n-1) + \Theta(n) & \textrm{if } n > 1. \end{cases}$

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, dh $T(n-1) + \Theta(n)$ .

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

algorithm-analysis runtime-analysis recurrence-relation sorting Aseem Bansal
quelle

Sie könnten an unseren Referenzfragen interessiert sein . Insbesondere ist der Begriff "Laufzeit" unscharf, die Wiederholung mit

Θ

$\Theta$ -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:

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

{\begin{matrix} 1 & , n = 1 \\ T. (n - - 1) + Θ (l Ö G n) & , Ö t h e r w ich s e \end{matrix}}}

$\begin{Bmatrix} 1 & ,\ n=1\\ T(n-1)\ +\ \Theta(log\ n) & ,\ otherwise \end{Bmatrix}$
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

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