Lekcja: "Algorytmy sortujące - sortowanie przez wstawianie, sortowanie przez wybór"
W poniższej tabeli przedstawiono przykładowe zapisy klas złożoności obliczeniowej algorytmów.
O(n)
Algorytm o liniowej zależności czasu wykonania od ilości danych. Dwukrotny wzrost liczby przetwarzanych danych powoduje dwukrotny wzrost czasu wykonania. Tego typu złożoność powstaje, gdy dla każdego elementu należy wykonać stałą liczbę operacji.
O(n2)
Algorytm, w którym czas wykonania rośnie z kwadratem liczby przetwarzanych elementów. Dwukrotny wzrost liczby danych powoduje czterokrotny wzrost czasu wykonania. Tego typu złożoność powstaje, gdy dla każdego elementu należy wykonać ilość operacji proporcjonalną do liczby wszystkich elementów.
O(n log n)
Dobre algorytmy sortujące mają taką właśnie złożoność obliczeniową. Czas wykonania przyrasta dużo wolniej od wzrostu kwadratowego. Tego typu złożoność powstaje, gdy zadanie dla n elementów można rozłożyć na dwa zadania zawierające po połowie elementów.
O(n!)
O(an)
Bardzo pesymistyczne algorytmy, czas wykonania rośnie szybko wraz ze wzrostem liczby elementów wejściowych, czyli znalezienie rozwiązania może zająć najszybszym komputerom bardzo dużo czasu. Takich algorytmów należy unikać.
