Wpisany przez Michał Knasiecki
poniedziałek, 01 sierpnia 2005 22:22
Jest to jeden z najważniejszych parametrów charakteryzujących
algorytm. Decyduje on o efektywności całego programu. Podstawowymi zasobami
systemowymi uwzględnianymi w analizie algorytmów są czas działania oraz
obszar zajmowanej pamięci.
Na złożoność czasową składają się dwie wartości: pesymistyczna,
czyli taka, która charakteryzuje najgorszy przypadek działania oraz
oczekiwana.
Najczęściej algorytmy mają złożoność czasową proporcjonalną do funkcji:
Zobacz też rzędy wielkości funkcji
- log(n)- złożoność logarytmiczna
- n - złożoność liniowa
- nlog(n) - złożoność liniowo-logarytmiczna
- n2 - złożoność kwadratowa
- nk - złożoność wielomianowa
- 2n - złożoność wykładnicza
- n! - złożoność wykładnicza, ponieważ n!>2n już od n=4
Zobacz też rzędy wielkości funkcji
Poprawiony: poniedziałek, 15 sierpnia 2005 23:53
Komentarze
Tak tak dokładnie tak
log(n)
n
nlog(n)
n^2
n^3
...
2^n
3^n
...
n!
Na załączonym wykresie widać jak czas wykonania programu rośnie w zależności od wielkości rozwiązywanego problemu.