Durchschnittliche Fallanalyse der Einfügungssorte, die in Kenneth Rosens "diskrete Mathemathematik und seiner Anwendung" behandelt wird

Question

Ich ging durch "diskrete Mathematik und seine Anwendung" von Kenneth Rosen , wo ich auf den folgenden Algorithmus der Insertionsart und auch seiner Analyse stieß. Der Algorithmus unterscheidet sich ganz von der, die sich in den ClRs befasst, sodass ich den gesamten Algorithmus unten geteilt habe. Beachten Sie, dass sie eine Maschine betrachtet haben, in der nur Vergleiche in Betracht gezogen werden, als er erheblich ist und somit entsprechend vorgegangen ist. Das Problem, das ich konfrontiert, ist in dem hier fett gedruckten Analyseanteil. Darüber hinaus wurden die spezifischen Zweifel, die ich habe, von mir zum Ende dieser Frage ausgewichtet worden.

Algorithmus die Einfügungssorte.

---

Prozedur einfügungssort ( $ a_1, a_2, ..., a_n $ : echte Zahlen mit $ n \ geqslant 2 $ )

generasacodicetagpre.

Die Einfügungssortierung: Die Einfügungssort ist ein einfacher Sortieralgorithmus, der jedoch normalerweise nicht das effizienteste ist. So sortieren Sie eine Liste mit $ N $ Elemente, beginnt die Einfügungssät mit dem zweiten Element. Der Einfügungssort vergleicht dieses zweite Element mit dem ersten Element und fügt ihn vor dem ersten Element ein, wenn er das erste Element nicht überschreitet und nach dem ersten Element, wenn er das erste Element überschreitet, wenn er das erste Element überschreitet. An diesem Punkt befinden sich die ersten beiden Elemente in der richtigen Reihenfolge. Das dritte Element wird dann mit dem ersten Element verglichen, und wenn er größer als das erste Element ist, wird er mit dem zweiten Element verglichen; Es wird in die richtige Position unter den ersten drei Elementen eingesetzt.

Im Allgemeinen, in der $ y $ ter Schritt der Einfügungssortierung, der $ y $ Das Element der Liste wird in die richtige Position in der Liste der zuvor sortierten $ J - 1 $ Elemente eingesetzt. Um den $ y $ tiges Element in der Liste einzufügen, wird eine lineare Suchtechnik verwendet. Der $ y $ Das Element ist nacheinander verglichen mit dem bereits sortierten $ J - 1 $ Elemente zu Beginn der Liste, bis das erste Element, das nicht kleiner als dieses Element ist, gefunden oder bis er mit allen $ J - 1 $ Elemente verglichen wurde; Der $ y $ Das Element wird in die richtige Position eingefügt, so dass der erste $ J $ Elemente sortiert ist . Der Algorithmus wird fortgesetzt, bis das letzte Element in der richtigen Position relativ zur bereits sortierten Liste der ersten $ N - 1 $ Elemente eingesetzt wird. Die Einfügungssort ist in Pseudocode in einem Algorithmus oben beschrieben.

Durchschnittskofferkomplexität der Einfügungssorgart : Was ist die durchschnittliche Anzahl der Vergleiche, die von der Einfügungssorgart zur Sortierung von $ N $ verwendet werden soll verschiedene Elemente?

0 Math-Container "> $ A_1, A_2, ..., A_N $ von $ n $ verschiedene Elemente. Dann $ e (x) $ ist die durchschnittliche Anzahl der verwendeten Vergleiche. (Erinnern Sie sich, dass in Schritt $ i $ für $ i= 2, ..., n $ , die Einfügungssort einfügt den $ i $ tiges Element in der Originaliste in die richtige Position in der sortierten Liste der ersten $ i - 1 $ Elemente der Originalliste.)

wir lassen $ x_i $ Seien Sie die Zufallsvariable, die der Anzahl der Vergleiche verwendet, die zum Einfügen von $ A_I $ in die richtige Position nach dem ersten $ I - 1 $ Elements $ A_1, A_2, ..., A_ { I-1} $ wurde sortiert. Weil

$ x= x_2 + x_3 + ··· + x_n $ ,

Wir können die Linearität der Erwartungen verwenden, um zu dem Schluss, dass

$ E (x)= E (x_2 + x_3 + ··· + x_n)= e (x_2) + e (x_3) + ··· + e (x_n) . $

, um $ e (x_i) $ für $ i= 2, 3, ..., N $ , let $ p_j (k) $ Bezeichnen Sie die Wahrscheinlichkeit, dass der größte der ersten $ J $ Elemente in der Liste erfolgt auf der $ K $ tiger Position, dh dieser $ max (A_1, a_2, ..., a_j)= a_k $ , wobei $ 1 ≤ k ≤ j $ . Da die Elemente der Liste zufällig verteilt sind, ist es wahrscheinlich für das größte Element unter der Tanne wahrscheinlich

ST $ J $ Elemente, die in jeder Position auftreten können. Folglich $ p_j (k)=frac {1} {j} $ .f $ x_i (k) $ < / span> entspricht der Anzahl der Vergleiche, die von der Einfügungssorgart verwendet werden, wenn $ a_i $ in den $ K $ eingefügt wird ten Position in der Liste einmal $ A_1, A_2, ..., A_ {i-1} $ sortiert wurde, er folgt diesem $ x_i (k)= k $ . Da es möglich ist, dass $ A_I $ in einem der ersten $ I $ -Positionen eingefügt wird, finden wir das

$ E (x_i) $ = $$ \ SUM_ {K= 1} ^ {i} p_i (k ) .X_i (k)=sum_ {k= 1} ^ {i} \ frac {1} {i} .k=frac {1} {i} \ sum_ {k= 1} ^ {i} k=frac {1} {i}. \ frac {i (i + 1)} {2}=frac {i + 1} {2} $$

es folgt das

$ E (x) $ = $$ \ Sum_ {i= 2} ^ {n} E (x_i )=sum_ {i= 2} ^ {n} \ frac {i + 1} {2}=frac {n ^ {2} + 3n -4} {4} $$

mein Zweifel

---

jetzt hier, während wir die Berechnung von $ e (x_i) $ in Betracht ziehen, in Betracht ziehen, dass wir die Wahrscheinlichkeit des maximalen Elements zwischen $ A_1, A_2, ..., A_I $ in Position $ K $ . Dann sagen sie, dass die Anzahl der Vergleiche, wenn $ a_i $ in den $ K $ der Position installiert ist In der Liste $ A_1, A_2, ..., A_ {I-1} $ (das bereits sortiert ist) ist $ k $ . Warum berücksichtigen sie das Einfügen von $ a_i $ in die Position des Maximums der Elemente $ A_1, A_2, .. ., A_i $ . $ A_I $ , wie der Algorithmus in der ersten Position platziert werden soll (während Sie das Array von links abcannen), wenn ein Element gefunden wird, das $ \ geqslant a_i $ und nicht das maximale Element des Unterlisten $ A_1, A_2, ..., A_I $ .

wechselover sagen sie, dass das maximale Element des Sublist $ a_1, a_2, ..., a_i $ eine beliebige Position ist $ K $ th und die Wahrscheinlichkeit, dass es $ \ frac {1} {i} $ ist. Wenn wir jedoch sehen, dass $ A_1, A_2, ..., A_ {I-1} $ sortiert ist, dann die max. $ a_1, a_2, ..., a_i $ ist entweder $ a_ {i-1} $ oder $ a_i $ .

Answer 1

Die Wahrscheinlichkeit $ 1 / I $ ist korrekt, da es sich auf die relative Reihenfolge von $ a_1, \ ldots bezieht,A_i $ Vor dem Sortieren der ersten $ I-1 $ Elemente.

Das Argument erscheint jedoch falsch.Die relevante Wahrscheinlichkeit ist nicht $ P_I (k) $ , sondern eher $ q_i (k) $ , wasist die Wahrscheinlichkeit, dass $ a_i $ der $ k $ 'tig kleinstes Element aus $ A_1, \ ldots, a_i $ ( vor sortieren).Diese Wahrscheinlichkeit ist $ 1 / I $ , unabhängig von $ K $ .