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{\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