Złożoność czasowa

There are different measurements of the speed of any given algorithm. Dla podanej wielkości wejścia N, mogą być opisane następująco:

Nazwa	Szybkość	Opis	Formuła	Przykład
factorial time	najwolniejszy	takes an amount of time proportional to N raised to the Nth power	N!	Brute force solution to Traveling Salesman Problem
czas wykładniczy	wolny	takes an amount of time proportional to a constant raised to the Nth power	KN	Brute force solution to Rubik's Cube
czas wielomianowy	szybki	takes an amount of time proportional to N raised to some constant power	NK	Comparison sorts (bubble, insertion, selection sort)
czas liniowo-logarytmiczny	szybszy	takes an amount of time between linear and polynomial	N * log(N)	Liniowo-logarytmiczne sortowanie (quicksort, heapsort, mergesort)
czas liniowy	jeszcze szybszy	takes an amount of time directly proportional to N	K * N	Iterowanie po tablicy
czas logarytmiczny	dużo szybszy	takes an amount of time proportional to the logarithm of N	K * log(N)	Binary Search
czas stały	najszybszy	takes a fixed amount of time, no matter how large the input is	K	Array index lookup

Analiza złożoności

Operacje mogą mieć różną złożoność czasową zależną od rozmiaru/zbioru danych wejściowych. Wyróżniamy następujące rodzaje analizy złożoności czasowej:

Nazwa	Opis	Przykład
optymistyczna	Przypadek gdy operacja wykonuje się możliwie najszybciej	Bubblesort (sortowanie bąbelkowe) ma optymistyczną złożoność czasową rzędu N
oczekiwana	Przypadek gdy operacja wykonuje się w czasie charakteryzującym większość przypadków	Quicksort ma oczekiwaną złożoność czasową rzędu N * log(N)
pesymistyczna	Przypadek gdy operacja wykonuje się możliwie najwolniej	Quicksort ma pesymistyczną złożoność czasową rzędu N2
pesymistyczna zamortyzowana	Średnia z pesymistycznych czasów wykonania nieskończonej liczby operacji	vector::push_back() ma zamortyzowaną pesymistyczną złożoność czasową rzędu K (stałą)

Choosing the right algorithm depends upon which cases you expect your application to encounter. For example, an application that must protect itself from malicious input will avoid naive implementations of quicksort, which has a worst-case time complexity of N² despite having one of the fastest average-case time complexities compared to all other sorts.