złożoność obliczeniowa

Opis szczegółowy

Złożoność obliczeniowa jest to ilość podstawowych operacji jakie trzeba wykonać, aby został zrealizowany dany algorytm, posiadając określoną ilość danych wejściowych. Złożoność obliczeniowa oznaczana jest przez dużą literę O.

Rzędy złożoności obliczeniowej

Formalny zapis	Opis	Szybkość algorytmu
O(C*1)	stała złożoność - algorytm wykonuje się w stałej ilości operacji, niezależnie od ilości danych.	najszybszy
O(C*log2(n))	złożoność logarytmiczna - algorytm wykonuje logarytmiczną ilość operacji w stosunku do ilości danych wejściowych; n jest to ilość danych wejściowych. Podstawa logarytmu zazwyczaj wynosi 2, jednak czasami może być większa (np. w B-drzewach).	bardzo szybki
O(C*n)	złożoność liniowa - algorytm wykonuje wprost proporcjonalną ilość operacji do ilości danych wejściowych.	szybki
O(C*n*log2(n))	złożoność liniowo-logarytmiczna.	szybki
O(C*n2)	złożoność kwadratowa - ilość operacji algorytmu jest wprost proporcjonalna do ilości danych wejściowych podniesionej do potęgi drugiej.	niezbyt szybki
O(C*nX)	złożoność wielomianowa - ilość operacji algorytmu jest wprost proporcjonalna do ilości danych wejściowych podniesionej do potęgi X, gdzie X jest stałą większą lub równą 2.	wolny
O(C*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 ilości danych wejściowych.	bardzo wolny

C - jest to stała, która może mieć wartość zarówno 1 jak i 1000000. Zazwyczaj stała ta jest tak mała, że jest ona pomijalna przy podawaniu złożoności obliczeniowej algorytmów. Wartość C wynosi najczęściej 1 lub 2.

Linki zewnętrzne

• http://cpp0x.pl/kursy/Teoria-w-Informatyce/Zlozonosc-obliczeniowa/Rzedy-zlozonosci-obliczeniowej/427