Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Autor: Piotr Szawdyński
Biblioteki C++

Rzędy złożoności obliczeniowej

[lekcja] Rozdział odpowiada na pytanie w jaki sposób ocenia się złożoność obliczeniową algorytmów.
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ść czasowaOpisSzybkość 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
Poprzedni dokument Następny dokument
Teoria złożoności obliczeniowej Rodzaje problemów obliczeniowych