FANDOM


Main-qimg-95eba275e86a62b3d29a80514631bccc

Wykres porównujący złożoności

Złożoność czasowa
(ang. time complexity) jest sposobem na ocenę optymalizacji i szybkości algorytmu. Zazwyczaj przedstawiana jst w tak zwanym zapisie dużego O (ang. big O notation). Zapis taki pokazuje w jaki sposób ilość wykonanych przez program operacji zależy od wielkości i ilości danych wejściowych.

Wyróżniamy kilka najważniejszych rzędów złożoności obliczeniowej

  • Złożoność stała - czyli program wykona tyle samo kroków dla każdych danych wejściowych. Zapisywana jako O(1)
  • Złożoność logarytmicza - czyli ilość operacji zależna logarytmicznie od ilości danych wejściowych. Zapisywana jako O(log(n))
  • Złożoność liniowa - czyli ilość operacji zależna liniowo od ilości danych wejściowych. Zapisywana jako O(n ^ 2)
  • Złożoność kwadratowa - czyli ilość operacji zależna kwadratowo od ilości danych wejściowych. Zapisywana jako O(n ^ 2)
  • Złożoność wykładnicza - czyli ilość operacji zależna wykładniczo od ilości danych wejściowych. Zapisywana jako O(2 ^ n)

PrzykładyEdytuj

Weźmy przykładowy algorytm i sprobujmy określić jego złożoność czasową.

 procedure nasz_algorytm ( n : liczba całkowita, większa lub równa zero )
   tab : tablica liczb całkowitych
   
   for ( i = 0; i < n; i++ ) do
     wczytaj liczbę do tab [i]
   end
   
   maksimum : liczba całkowita
   maksimum = 0
   
   for ( i = 0; i < n; i++ ) do
     if tab [i] > maksimum then
       maksimum = tab [i]
     end if
   end
   
   wypisz maksimum
 end procedure

Powyższy algorytm wczytuje tablicę n liczb i wypisuje największą liczbę. Ponieważ w tym celu wykonuje n (pętla raz przechodzi przez tablicą) operacji złożoność zapiszemy jako O(n). Zamieńmy teraz pętlę z następującą.

 for ( i = 0; i < n; i++ ) do
   if tab [i] > maksimum then
     maksimum = tab [i]
   end if
   
   for ( j = i; j < n; j++ ) do
     if tab [j] > tab [i] then
       maksimum = tab [j]
     end if
   end
 end

W powyższym (bezsensownym) algorytmie nie tylko porównujemy liczbę z tablicy do maksimum, ale także wyszukujemy wartości większej w pozostałej części tablicy. W ten sposób dla kolejnych liczb wykonamy n, n - 1, ..., 1 operacji porównania. Sumując ten ciąg otrzymamy \tfrac{n^2}{2} + \tfrac{n}{2} - 1 operacji. Rząd złożoności wynosi więc O(n^2).