Złożoność oczekiwana

Złożoność oczekiwana określa złożoność średnią, czyli wartość oczekiwaną zmiennej losowej $f.$ Jeśli wszystkie dane są jednakowo prawdopodobne (z prawdopodobieństwem niezerowym), wtedy wyraża się ona wzorem:

${\frac {\displaystyle \sum _{d\in D}f(d)}{|D|}},$

gdzie:

$D$ – zbiór wszystkich możliwych danych wejściowych,

$d$ – jeden z elementów tego zbioru,

$f$ – funkcja, która dla danego $d$ zwraca liczbę operacji.

Zobacz też

• złożoność obliczeniowa
• złożoność pesymistyczna