maj 09 2016 9 maja 2016 9 maja 2016 przez Michał Franczak

Złożoność algorytmu

Napisano w

Pod tym adresem możemy przypomnieć sobie o złożoności i poprawności algorytmów – http://mfranczak.pl/46-zlozonosc-i-efektywnosc-algorytmow/

plik do ćwiczeń – Złożoność algorytmu

 

Rzędy złożoności czasowej

Złożoność czasowa Opis Szybkość algorytmu przykład 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 Sort. kubełkowe
O(n*log2(n)) złożoność liniowo-logarytmiczna

  • n jest to liczba danych wejściowych.
 szybki Sort. Przez scalanie, quicksort,
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 Sort. Bąbelkowe, przez wstawianie,
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