Laufzeitanalyse: Unterschied zwischen den Versionen

(4 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)

Zeile 29:

Man berechnet ihn, indem man alle möglichen Eingaben durchspielt und gewichtet. Die Formel für den Erwartungswert <math>E(T)</math> lautet:

* <math>p_i</math> ist die Wahrscheinlichkeit ~~für einen bestimmten Fall~~ <math>i</math>.

Hierbei bedeuten die Variablen:

* <math>t_i</math> ist die Anzahl der Rechenschritte, die der Algorithmus ~~in diesem Fall~~ braucht.

* <math>F</math> ist die Menge aller theoretisch möglichen Eingaben der Größe <math>n</math> (z. B. alle möglichen Anordnungen einer Zahlenliste).

* <math>|F|</math> (Betragsstriche) steht in der Mathematik für die Mächtigkeit einer Menge. Es ist also die '''exakte Anzahl''' aller dieser möglichen Eingaben.

* <math>p_i</math> ist die Wahrscheinlichkeit, dass genau die spezifische Eingabe <math>i</math> auftritt.

* <math>t_i</math> ist die Anzahl der Rechenschritte, die der Algorithmus für exakt diese Eingabe <math>i</math> braucht.

Für die Schule gehen wir meistens von einer '''Gleichverteilung''' aus: Jeder ~~Fall~~ tritt mit derselben Wahrscheinlichkeit auf.

Für die Schule gehen wir meistens von einer '''Gleichverteilung''' aus: Jeder Eingabefall tritt mit exakt derselben Wahrscheinlichkeit auf.

=== Average-Case der Linearen Suche ===

Zeile 62:

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 97:

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 29: / Zeile 29: @@
 Man berechnet ihn, indem man alle möglichen Eingaben durchspielt und gewichtet. Die Formel für den Erwartungswert <math>E(T)</math> lautet:
-<math>E(T) = \sum_{i=1}^{|E|} p_i \cdot t_i</math>
+<math>E(T) = \sum_{i=1}^{|F|} p_i \cdot t_i</math>
-* <math>p_i</math> ist die Wahrscheinlichkeit für einen bestimmten Fall <math>i</math>.
+Hierbei bedeuten die Variablen:
-* <math>t_i</math> ist die Anzahl der Rechenschritte, die der Algorithmus in diesem Fall braucht.
+* <math>F</math> ist die Menge aller theoretisch möglichen Eingaben der Größe <math>n</math> (z. B. alle möglichen Anordnungen einer Zahlenliste).
+* <math>|F|</math> (Betragsstriche) steht in der Mathematik für die Mächtigkeit einer Menge. Es ist also die '''exakte Anzahl''' aller dieser möglichen Eingaben.
+* <math>p_i</math> ist die Wahrscheinlichkeit, dass genau die spezifische Eingabe <math>i</math> auftritt.
+* <math>t_i</math> ist die Anzahl der Rechenschritte, die der Algorithmus für exakt diese Eingabe <math>i</math> braucht.
-Für die Schule gehen wir meistens von einer '''Gleichverteilung''' aus: Jeder Fall tritt mit derselben Wahrscheinlichkeit auf.
+Für die Schule gehen wir meistens von einer '''Gleichverteilung''' aus: Jeder Eingabefall tritt mit exakt derselben Wahrscheinlichkeit auf.
 === Average-Case der Linearen Suche ===
@@ Zeile 62: / 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 97: / 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]]