Wybierz interesującą Cię pozycję:



























Złożoność obliczeniowa algorytmu



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:



* 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







Wykorzystanie drzew w analizie algorytmów.


Drzewo algorytmu może służyc do określania liczby operacji n\wykonywanych przez algortym. Zilustrujemy to na przykładzie drzewa przedstawionego na rysunku 1. Dla uzyskania konkretnego wyniku, który znajduje się w wierzchołku wiszacym drzewa, liczba wykonanych porównań równa się liczbie wierzchołków oośrednich na drodze od korzenia ( licząc również korzeń ) do tego wierzchołka-tę liczbe nazywamy długością drogi. Na przykład, jeśli dane trzy liczby a, b i c spełniają nierowności c<=a<=b lub c<=b<=a, to algorytm wykonuje 2 porownania, a w pozostałych przypadkach-wykonuje 3 porównania. Największa długość drogi z korzenia do wierzchołka końcowego w drzewie nazywa sie WYSOKOŚCIĄ DRZEWA.







Drzewo na rys.1 ma wysokość 3. Wysokość drzewa to najwieksza liczba operacji wykonywanych w algorytmie dla dowolnego układu danych. W algorytmie wielkość ta nazywa sie ZŁOŻONOŚCIĄ OBLICZENIOWĄ ALGORYTMU. Jak ilustruje to nasz przykład, jest to ZŁOŻONOŚĆ PESYMISTYCZNA lub ZŁOŻONOŚĆ NAJGORSZEGO PRZYPADKU, gdyż w niektórych przypadkach algorytm może działać szybciej. W algorytmice rozważa sie również PAMIĘCIOWĄ ZŁOŻONOŚĆ ALGORYTMOW, w której określa sie wielkość pamięci komputera, potrzebnej do przechowania danych, oraz pośrednich i końcowych wyników obliczeń.











Tabela
Algorytmy i ich złożoność
AlgorytmZłożoność obliczeniowa
Dziel i zwycięzaj(3n/2)-2
Min, Max2n-3
Porządkowanie przez wybór(n*(n-1))/2
Scalanie dwóch uporządkowanych ciągów(n-1)
Merge Sort-porządkowanie przez scalanie (p,q,x)nlog2n