Średnia złożoność algorytmu jest to ilość danego źródła, na ogół czasu , wykorzystywanych przez algorytm w czasie jego działania na wejście procesu opracowanego według danego rozmieszczenia . Jest to zatem średnia złożoności, ważona między różnymi możliwymi danymi wejściowymi zgodnie z wybranym rozkładem. Najczęściej nie określił dystrybucję i pośrednio korzystać z rozkładu równomiernego ( czyli do dyskretnego jednolite prawo w dyskretnym przypadku), to znaczy, że wszystkie wejścia są uważane za jednakowo prawdopodobne.
Jest to ważna miara do analizy złożoności algorytmów i kontrastuje ze złożonością najgorszego przypadku, która uwzględnia maksymalną złożoność algorytmu dla wszystkich możliwych danych wejściowych.
Różne przyczyny mogą uzasadniać badanie średniej złożoności algorytmu. Niektóre problemy mają bardzo dużą złożoność w najgorszym przypadku , ale wpisy odpowiadające tym przypadkom występują w praktyce bardzo rzadko, więc średnio złożoność jest bardziej użyteczną miarą wydajności algorytmu. Służy więc do porównywania ze sobą działania różnych algorytmów, zwłaszcza gdy mają one taką samą złożoność w najgorszym przypadku lub gdy wiemy, że nie ma potrzeby rozważania najgorszego przypadku. Ponieważ mamy dodatkowe informacje o wpisach które zostaną omówione w praktyce.
Analiza średniej złożoności dostarcza również narzędzi i technik do generowania trudnych przypadków problemów, które można na przykład wykorzystać w takich dziedzinach, jak kryptografia .
Najczęściej średnią złożoność oblicza się, biorąc pod uwagę, że wszystkie możliwe dane wejściowe są równie prawdopodobne. To sprawia, że obliczenia są łatwiejsze do wykonania, ale niekoniecznie tak się dzieje w praktyce.
Czasami najgorsze przypadki występują z większym prawdopodobieństwem niż inne wpisy. Na przykład często ma to miejsce w przypadku algorytmu szybkiego sortowania , którego złożoność wynosi średnio , ale którego złożoność w najgorszym przypadku jest i jest osiągana dla wpisów już posortowanych. Jednym ze sposobów podejścia do „rzeczywistego” prawdopodobieństwa różnych możliwych danych wejściowych jest użycie miary Levina, zdefiniowanej jako funkcja złożoności Kołmogorowa wg . M. Li i P. Vitanyi wykazali w ten sposób, że średnia złożoność sortowania szybkiego ważona miarą Levina była podobna do złożoności w najgorszym przypadku.
W przypadku algorytmów sortowania złożoność uśredniona w rozkładzie jednorodnym została szeroko zbadana. Niektóre rodzaje, takie jak sortowanie szybkie lub sortowanie grzebieniowe, mają średnio optymalną złożoność, ale nie w najgorszym przypadku. Inne są optymalne zgodnie z dwoma miarami, takie jak sortowanie przez scalanie , jeszcze inne nie są optymalne dla żadnej z dwóch miar, tak jest na przykład w przypadku sortowania przez wstawianie .