Rzędy złożoności obliczeniowej

Kolejnym interesującym aspektem wynikającym z teorii złożoności obliczeniowej są rzędy złożoności obliczeniowej. Teoria ta pozwala bowiem określić jak wydajny jest dany algorytm pod kątem zużycia pamięciowego czy też czasowego. W dalszej części niniejszego rozdziału została umieszczona tabela, która zawiera zestawienie powszechnie używanych rzędów złożoności. Tabela o której mowa została opracowana pod kątem złożoności czasowej. Analogiczną tabelę można stworzyć do prezentacji rzędów złożoności pamięciowej. Złożoność pamięciowa algorytmów z punktu widzenia współczesnej informatyki jest znacznie rzadziej analizowana, więc nie ma powodów aby rozwodzić się nad tym problemem.

Rzędy złożoności czasowej

Złożoność czasowa	Opis	Szybkość algorytmu
O(1)	stała złożoność – algorytm wykonuje się w stałej ilości operacji, niezależnie od liczby danych wejściowych.	najszybszy
O(log2(n))	złożoność logarytmiczna – algorytm wykonuje logarytmiczną ilość operacji w stosunku do liczby danych wejściowych. n jest to liczba danych wejściowych; podstawa logarytmu zazwyczaj wynosi 2, jednak czasami może być większa (np. w B-drzewach).	bardzo szybki
O(n)	złożoność liniowa – algorytm wykonuje wprost proporcjonalną ilość operacji do liczby danych wejściowych. n jest to liczba danych wejściowych.	szybki
O(n*log2(n))	złożoność liniowo-logarytmiczna n jest to liczba danych wejściowych.	szybki
O(n2)	złożoność kwadratowa – ilość operacji algorytmu jest wprost proporcjonalna do liczby danych wejściowych podniesionej do potęgi drugiej. n jest to liczba danych wejściowych.	niezbyt szybki
O(nX)	złożoność wielomianowa – ilość operacji algorytmu jest wprost proporcjonalna do liczby danych wejściowych podniesionej do potęgi X. n jest to liczba danych wejściowych; X jest stałą o dowolnej wartości. Uwaga! Pamiętaj, że zarówno funkcja liniowa jak i funkcja kwadratowa są również wielomianami. W informatyce posługując się terminem złożoności wielomianowej zazwyczaj mamy na myśli algorytmy, których złożoność obliczeniowa (lub pamięciowa) jest co najmniej kwadratowa.	wolny
O(Xn)	złożoność wykładnicza – ilość operacji algorytmu jest wprost proporcjonalna do stałej X większej lub równej 2, podniesionej do potęgi równej liczbie danych wejściowych. n jest to liczba danych wejściowych; X jest stałą większą niż 2.	bardzo wolny