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ż złożoność obliczeniowa złożoność pesymistyczna
Kategoria:Teoria obliczeń