Laufzeitanalyse: Unterschied zwischen den Versionen
Keine Bearbeitungszusammenfassung |
|||
| 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: | 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}^{| | <math>E(T) = \sum_{i=1}^{|F|} p_i \cdot t_i</math> | ||
Hierbei bedeuten die Variablen: | Hierbei bedeuten die Variablen: | ||
* <math> | * <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>| | * <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>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. | * <math>t_i</math> ist die Anzahl der Rechenschritte, die der Algorithmus für exakt diese Eingabe <math>i</math> braucht. | ||