Laufzeitanalyse: Unterschied zwischen den Versionen
Keine Bearbeitungszusammenfassung Markierung: Zurückgesetzt |
Markierung: Zurückgesetzt |
||
| Zeile 64: | Zeile 64: | ||
'''Fazit:''' Im Durchschnitt benötigt die lineare Suche <math>\frac{n+1}{2}</math> Vergleiche. Für die asymptotische Laufzeitanalyse ignorieren wir Konstanten und niederwertige Terme, sodass auch der Average-Case der linearen Suche in der Komplexitätsklasse <math>\mathcal{O}(n)</math> liegt. | '''Fazit:''' Im Durchschnitt benötigt die lineare Suche <math>\frac{n+1}{2}</math> Vergleiche. Für die asymptotische Laufzeitanalyse ignorieren wir Konstanten und niederwertige Terme, sodass auch der Average-Case der linearen Suche in der Komplexitätsklasse <math>\mathcal{O}(n)</math> liegt. | ||
=== | === Indikatorvariablen und die Harmonische Reihe === | ||
Bei einfachen Algorithmen reicht eine Gleichverteilung zur Herleitung oft aus. Bei komplexeren, teile-und-herrsche-basierten Algorithmen wie [[Quicksort]] reicht dies nicht mehr. Um den Average-Case von Quicksort (<math>\mathcal{O}(n \log n)</math>) selbstständig ermitteln zu können, benötigt man zwei mathematische Werkzeuge: '''Indikatorzufallsvariablen''' und die '''Harmonische Reihe'''. | Bei einfachen Algorithmen reicht eine Gleichverteilung zur Herleitung oft aus. Bei komplexeren, teile-und-herrsche-basierten Algorithmen wie [[Quicksort]] reicht dies nicht mehr. Um den Average-Case von Quicksort (<math>\mathcal{O}(n \log n)</math>) selbstständig ermitteln zu können, benötigt man zwei mathematische Werkzeuge: '''Indikatorzufallsvariablen''' und die '''Harmonische Reihe'''. | ||
| Zeile 98: | Zeile 98: | ||
'''Erkenntnis für Quicksort:''' | '''Erkenntnis für Quicksort:''' | ||
Die Update-Operation wird im Average-Case also nur <math>\mathcal{O}(\log n)</math> Mal ausgeführt, obwohl das Array <math>n</math> Elemente hat. Genau dieses Prinzip – das Aufsummieren von stochastischen Wahrscheinlichkeiten der einzelnen Array-Elemente, die zu einer harmonischen Reihe und damit zu einem logarithmischen Faktor führen – ist der mathematische Schlüssel, um die Average-Case-Laufzeit von <math>\mathcal{O}(n \log n)</math> bei Quicksort herzuleiten. | Die Update-Operation wird im Average-Case also nur <math>\mathcal{O}(\log n)</math> Mal ausgeführt, obwohl das Array <math>n</math> Elemente hat. Genau dieses Prinzip – das Aufsummieren von stochastischen Wahrscheinlichkeiten der einzelnen Array-Elemente, die zu einer harmonischen Reihe und damit zu einem logarithmischen Faktor führen – ist der mathematische Schlüssel, um die Average-Case-Laufzeit von <math>\mathcal{O}(n \log n)</math> bei Quicksort herzuleiten. | ||
== Beispiel: Laufzeitanalyse von Insertion Sort == | == Beispiel: Laufzeitanalyse von Insertion Sort == | ||