Laufzeitanalyse: Unterschied zwischen den Versionen

(2 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)

Zeile 65:

int v, i, j;

for (i = 1; i < zSortfeld.length; i++) {

~~c++; // Zähler für Vergleiche~~

if (zSortfeld[i] < zSortfeld[i - 1]) {

v = zSortfeld[i];

Zeile 100:

Zeile 99:

=== 3. Average-Case-Szenario (Durchschnittlicher Fall) ===

~~Die Werte im~~ Array sind ~~völlig zufällig verteilt~~.

Wir sortieren ein Array der Länge <math>n</math>. Wir nehmen an, alle Permutationen (Anordnungen) der Zahlen sind gleich wahrscheinlich. Der Algorithmus fügt nacheinander jedes Element an Index <math>i</math> (von Position 2 bis <math>n</math>) in den bereits sortierten vorderen Teil der Länge <math>i-1</math> ein.

* '''~~Verhalten~~:''' ~~Im Durchschnitt müssen wir ein Element nicht~~ bis ganz ~~an den Anfang schieben (wie im Worst-Case~~), ~~sondern nur bis zur~~ '''~~Hälfte~~''' des ~~bisher sortierten Bereichs~~.

* '''~~Aufwand~~:''' Die ~~Anzahl~~ der ~~Vergleiche halbiert~~ sich ~~grob im Vergleich zum Worst-Case~~. ~~Der Aufwand liegt~~ bei ~~ca.~~ <math>\frac{1}{2} \cdot \frac{c}{2}n^2</math>.

* '''Schritt 1: Wahrscheinlichkeit bestimmen.''' Beim Einfügen des <math>i</math>-ten Elements gibt es genau <math>i</math> mögliche Zielpositionen (von ganz vorne bis zu seinem aktuellen Platz ganz hinten). Da die ursprüngliche Reihenfolge zufällig ist, ist jede dieser Positionen gleich wahrscheinlich. Die Wahrscheinlichkeit für jede Position ist also <math>p = \frac{1}{i}</math>.

* '''~~Komplexität~~:''' ~~Wie wir gelernt haben, ignoriert die Groß-~~O-Notation ~~konstante Brüche~~ (wie <math>\frac{1}{4}</math>)~~. Es bleibt bei~~ der ~~höchsten Potenz: Das Wachstum ist und bleibt quadratisch. Die Komplexität lautet also weiterhin~~ <math>\mathcal{O}(n^2)</math>.

* '''Schritt 2: Schritte zählen.''' Das Finden der richtigen Position ist wie eine rückwärtsgerichtete lineare Suche. Im besten Fall (das Element ist bereits größer als alle vorherigen und bleibt am Ende) brauchen wir 1 Vergleich. Im Durchschnitt muss das Element mit der Hälfte der bereits sortierten Elemente verglichen werden, um seinen Platz zu finden. Der durchschnittliche Aufwand (Vergleiche) für das Einfügen des <math>i</math>-ten Elements liegt daher bei etwa <math>\frac{i}{2}</math>.

* '''Schritt 3: Erwartungswert berechnen.''' Um die Gesamtlaufzeit zu erhalten, summieren wir den durchschnittlichen Aufwand für alle Elemente, die eingefügt werden müssen (von <math>i=2</math> bis <math>n</math>):

<math>E(T) \approx \sum_{i=2}^{n} \frac{i}{2}</math>

Wir klammern <math>\frac{1}{2}</math> aus:

<math>E(T) \approx \frac{1}{2} \cdot \sum_{i=2}^{n} i</math>

Die Summe der Zahlen von 1 bis <math>n</math> lässt sich wieder mit der '''Gaußschen Summenformel''' (kleiner Gauß) vereinfachen zu <math>\frac{n(n+1)}{2}</math>. Da unsere Summe aber erst bei <math>i=2</math> startet, ziehen wir die 1 (für den fehlenden Schritt <math>i=1</math>) ab:

<math>E(T) \approx \frac{1}{2} \cdot \left( \frac{n(n+1)}{2} - 1 \right) = \frac{n^2 + n - 2}{4} = \frac{1}{4}n^2 + \frac{1}{4}n - \frac{1}{2}</math>

'''Fazit:''' Im Durchschnitt braucht der Insertion Sort etwa <math>\frac{1}{4}n^2</math> Vergleiche. Da in der <math>\mathcal{O}</math>-Notation Konstanten wie <math>\frac{1}{4}</math> und Terme niedrigerer Ordnung (wie <math>\frac{1}{4}n - \frac{1}{2}</math>) wegfallen, gehört der Insertion Sort im Durchschnitt zur Klasse <math>\mathcal{O}(n^2)</math>.

[[Kategorie:Programmierung]]

[[Kategorie:AHR_I_Informatik_LK]]

@@ Zeile 65: / Zeile 65: @@
      int v, i, j;
      for (i = 1; i < zSortfeld.length; i++) {
-        c++; // Zähler für Vergleiche
          if (zSortfeld[i] < zSortfeld[i - 1]) {
              v = zSortfeld[i];
@@ Zeile 100: / Zeile 99: @@
 === 3. Average-Case-Szenario (Durchschnittlicher Fall) ===
-Die Werte im Array sind völlig zufällig verteilt.
+Wir sortieren ein Array der Länge <math>n</math>. Wir nehmen an, alle Permutationen (Anordnungen) der Zahlen sind gleich wahrscheinlich. Der Algorithmus fügt nacheinander jedes Element an Index <math>i</math> (von Position 2 bis <math>n</math>) in den bereits sortierten vorderen Teil der Länge <math>i-1</math> ein.
-* '''Verhalten:''' Im Durchschnitt müssen wir ein Element nicht bis ganz an den Anfang schieben (wie im Worst-Case), sondern nur bis zur '''Hälfte''' des bisher sortierten Bereichs.
-* '''Aufwand:''' Die Anzahl der Vergleiche halbiert sich grob im Vergleich zum Worst-Case. Der Aufwand liegt bei ca. <math>\frac{1}{2} \cdot \frac{c}{2}n^2</math>.
+* '''Schritt 1: Wahrscheinlichkeit bestimmen.''' Beim Einfügen des <math>i</math>-ten Elements gibt es genau <math>i</math> mögliche Zielpositionen (von ganz vorne bis zu seinem aktuellen Platz ganz hinten). Da die ursprüngliche Reihenfolge zufällig ist, ist jede dieser Positionen gleich wahrscheinlich. Die Wahrscheinlichkeit für jede Position ist also <math>p = \frac{1}{i}</math>.
-* '''Komplexität:''' Wie wir gelernt haben, ignoriert die Groß-O-Notation konstante Brüche (wie <math>\frac{1}{4}</math>). Es bleibt bei der höchsten Potenz: Das Wachstum ist und bleibt quadratisch. Die Komplexität lautet also weiterhin <math>\mathcal{O}(n^2)</math>.
+* '''Schritt 2: Schritte zählen.''' Das Finden der richtigen Position ist wie eine rückwärtsgerichtete lineare Suche. Im besten Fall (das Element ist bereits größer als alle vorherigen und bleibt am Ende) brauchen wir 1 Vergleich. Im Durchschnitt muss das Element mit der Hälfte der bereits sortierten Elemente verglichen werden, um seinen Platz zu finden. Der durchschnittliche Aufwand (Vergleiche) für das Einfügen des <math>i</math>-ten Elements liegt daher bei etwa <math>\frac{i}{2}</math>.
+* '''Schritt 3: Erwartungswert berechnen.''' Um die Gesamtlaufzeit zu erhalten, summieren wir den durchschnittlichen Aufwand für alle Elemente, die eingefügt werden müssen (von <math>i=2</math> bis <math>n</math>):
+<math>E(T) \approx \sum_{i=2}^{n} \frac{i}{2}</math>
+Wir klammern <math>\frac{1}{2}</math> aus:
+<math>E(T) \approx \frac{1}{2} \cdot \sum_{i=2}^{n} i</math>
+Die Summe der Zahlen von 1 bis <math>n</math> lässt sich wieder mit der '''Gaußschen Summenformel''' (kleiner Gauß) vereinfachen zu <math>\frac{n(n+1)}{2}</math>. Da unsere Summe aber erst bei <math>i=2</math> startet, ziehen wir die 1 (für den fehlenden Schritt <math>i=1</math>) ab:
+<math>E(T) \approx \frac{1}{2} \cdot \left( \frac{n(n+1)}{2} - 1 \right) = \frac{n^2 + n - 2}{4} = \frac{1}{4}n^2 + \frac{1}{4}n - \frac{1}{2}</math>
+'''Fazit:''' Im Durchschnitt braucht der Insertion Sort etwa <math>\frac{1}{4}n^2</math> Vergleiche. Da in der <math>\mathcal{O}</math>-Notation Konstanten wie <math>\frac{1}{4}</math> und Terme niedrigerer Ordnung (wie <math>\frac{1}{4}n - \frac{1}{2}</math>) wegfallen, gehört der Insertion Sort im Durchschnitt zur Klasse <math>\mathcal{O}(n^2)</math>.
 [[Kategorie:Programmierung]]
 [[Kategorie:AHR_I_Informatik_LK]]