Laufzeitanalyse: Unterschied zwischen den Versionen
Keine Bearbeitungszusammenfassung |
|||
| Zeile 36: | Zeile 36: | ||
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 Fall tritt mit derselben Wahrscheinlichkeit auf. | ||
=== | === Average-Case der Linearen Suche === | ||
Wir suchen eine bestimmte Zahl in einem Array der Länge <math>n</math>. Wir nehmen an, die Zahl ist im Array und jede Position ist gleich wahrscheinlich. | Wir suchen eine bestimmte Zahl in einem Array der Länge <math>n</math>. Wir nehmen an, die Zahl ist im Array und jede Position ist gleich wahrscheinlich. | ||
| Zeile 88: | Zeile 88: | ||
'''Erkenntnis für Quicksort:''' Obwohl das Array <math>n</math> Elemente hat, wird die Update-Operation im Durchschnitt nur logarithmisch oft (<math>\mathcal{O}(\log n)</math>) ausgeführt. Genau dieses stochastische Prinzip (das Aufsummieren von Einzelwahrscheinlichkeiten, die zu einem Logarithmus führen) ist der Schlüssel, um später selbst zu beweisen, dass Quicksort im Average-Case bei <math>\mathcal{O}(n \log n)</math> liegt. | '''Erkenntnis für Quicksort:''' Obwohl das Array <math>n</math> Elemente hat, wird die Update-Operation im Durchschnitt nur logarithmisch oft (<math>\mathcal{O}(\log n)</math>) ausgeführt. Genau dieses stochastische Prinzip (das Aufsummieren von Einzelwahrscheinlichkeiten, die zu einem Logarithmus führen) ist der Schlüssel, um später selbst zu beweisen, dass Quicksort im Average-Case bei <math>\mathcal{O}(n \log n)</math> liegt. | ||
== | == Laufzeitanalyse von Insertion Sort == | ||
Nun wenden wir unser Wissen auf das Sortierverfahren [[Insertion-sort|Insertion Sort]] (Sortieren durch Einfügen) an. | Nun wenden wir unser Wissen auf das Sortierverfahren [[Insertion-sort|Insertion Sort]] (Sortieren durch Einfügen) an. | ||