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 |
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 bombelkowe) 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 N2 despite having one of the fastest average-case time complexities compared to all other sorts.