Złożoność czasowa algorytmu
Wyjaśnienie terminu złożoność czasowa algorytmu
O
kreśla się, że algorytm ma złożoność czasową O(f(n)) wtedy, gdy jego czas wykonania dla danych o rozmiarze n można ograniczyć z góry przez pewną wielokrotność f(n). W praktyce oznacza to, że dla dużych n jego czas wykonania t(n) ≈ c f(n). W ten sposób można określać m.in. złożoność czasową (średnią i maksymalną) podstawowych operacji na strukturach danych biorąc za n liczbę elementów danych w strukturze. Ponieważ O(f(n)) jest zawsze górnym oszacowaniem złożoności, za lepsze uważa się oszacowanie przez funkcję wolniej rosnącą, ponieważ pozwala ono dokładniej określić czas wykonania dla dużych danych.
Operacje na złożonościach
Z
łożoność połączenia dwóch algorytmów to O(f(n)) + O(g(n)) = O(max(f(n), g(n)), gdzie max(f(n), g(n)) oznacza funkcję szybciej rosnącą. Złożoność wielokrotnego powtórzenia algorytmu to f(n) O(g(n)) = O(f(n) g(n)). Zwykle dobrze jest, aby spośród wielu możliwych podziałów złożonego algorytmu na mniejsze wybrać ten, który daje najlepsze oszacowanie.
Złożoność czasowa a czas wykonania — przykłady
Złożoność |
Przybliżony czas wykonania |
|||||
czasowa |
wzór |
n = 100 |
n = 1 000 |
n = 10 000 |
n = 100 000 |
n = 1 000 000 |
O(1) |
tn = c |
t100 |
t100 |
t100 |
t100 |
t100 |
O(log n) |
tn = c log2(n) |
t100 |
1,5 t100 |
2 t100 |
2,5 t100 |
3 t100 |
O(n) |
tn = c n |
t100 |
10 t100 |
100 t100 |
1000 t100 |
10 000 t100 |
O(n log n) |
tn = c n log2(n) |
t100 |
15 t100 |
200 t100 |
2500 t100 |
30 000 t100 |
O(n2) |
tn = c n2 |
t100 |
100 t100 |
10 000 t100 |
1 000 000 t100 |
100 000 000 t100 |
Porównanie efektywności niektórych struktur danych
Złożoność czasowa podstawowych operacji na niektórych strukturach danych
Struktura |
Liczba |
Koszt czasowy wykonania operacji |
|||||||||
danych |
pow- |
dodaj |
usuń* |
znajdź |
następny** |
suma |
|||||
|
tórzeń |
max. |
średni |
max. |
średni |
max. |
średni |
max. |
średni |
max. |
średni |
tablica |
1 |
O(1) |
O(1) |
O(n) |
O(n) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
O(n) |
|
n |
O(n) |
O(n) |
O(n2) |
O(n2) |
O(n2) |
O(n2) |
O(n) |
O(n) |
O(n2) |
O(n2) |
tablica |
1 |
O(n) |
O(n) |
O(n) |
O(n) |
O(log n) |
O(log n) |
O(1) |
O(1) |
O(n) |
O(n) |
posortowana |
n |
O(n2) |
O(n2) |
O(n2) |
O(n2) |
O(n log n) |
O(n log n) |
O(n) |
O(n) |
O(n2) |
O(n2) |
lista |
1 |
O(1) |
O(1) |
O(n) |
O(n) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
O(n) |
|
n |
O(n) |
O(n) |
O(n2) |
O(n2) |
O(n2) |
O(n2) |
O(n) |
O(n) |
O(n2) |
O(n2) |
lista |
1 |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
O(n) |
posortowana |
n |
O(n2) |
O(n2) |
O(n2) |
O(n2) |
O(n2) |
O(n2) |
O(n) |
O(n) |
O(n2) |
O(n2) |
drzewo |
1 |
O(n) |
O(log n) |
O(n) |
O(log n) |
O(n) |
O(log n) |
O(n) |
O(1) |
O(n) |
O(log n) |
BST |
n |
O(n2) |
O(n log n) |
O(n2) |
O(n log n) |
O(n2) |
O(n log n) |
O(n) |
O(n) |
O(n2) |
O(n log n) |
drzewo |
1 |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
O(1) |
O(log n) |
O(log n) |
AVL |
n |
O(n log n) |
O(n log n) |
O(n log n) |
O(n log n) |
O(n log n) |
O(n log n) |
O(n) |
O(n) |
O(n log n) |
O(n log n) |
*) Usuwanie elementu o podanym kluczu (a nie wskaźniku bądź indeksie w strukturze).
**) Odczytanie następnego elementu (lub jego wskaźnika) w przeglądaniu iteracyjnym.