Złożoność oczekiwana

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

gdzie:

– zbiór wszystkich możliwych danych wejściowych,
– jeden z elementów tego zbioru,
– funkcja, która dla danego zwraca liczbę operacji.

Zobacz teżEdytuj