Bez tytułu (5)

Analiza Porównawcza algorytmów - złożoność obliczeniowa algorytmów. Złożoność algorytmów:

•    Złożoność pamięciowa - wynika z liczby i rozmiaru danych jakie są wykorzystywane w algorytmie i jest szacowana poprzez założenie że rozmiar danych wejściowych wzrasta do nieskończoności.

Jest ona na ogól proporcjonalna do ilości danych użytych w programie czym więcej danych tym większa złożoność pamięciowa algorytmu. Z uwagi na organizację pamięci we współczesnych komputerach złożoność ta ma niewielki wpływ na możliwość realizacyj danego algorytmu (w praktyce dożo szybciej algorytm stanie się nieprzydatny z uwagi na złożoność obliczeniową niż pamięciową [jeden z wyjątków - Sortowanie przez zliczanie])

•    Złożoność obliczeniowa(czasow a) - wynika z liczby operacji wykonywanych w trakcie przebiegu algorytmu i jest szacowana poprzez założenie że rozmiar danych wejściowych wzrasta do nieskończoności.

Aby obliczyć złożoność czasową w algorytmie poszukujemy operacji wiodącej czyli takiej która zajmie procesorowi najwięcej czasu.

O(n) Złożoność liniowa Algorytm o liniowej zależności czasu wykonania od ilości danych. Dwukrotny wzrost liczby przetwarzanych danych powoduje dwukrotny wzrost czasu wykonania. Tego typu złożoność powstaje, gdy dla każdego elementu należy wykonać stałą liczbę operacji

0(n^A2) Złożoność kwadratowa Algorytm, w którym czas wykonania rośnie z kwadratem liczby przetwarzanych elementów Dwukrotny wzrost liczby danych powoduje czterokrotny wzrost czasu wykonania Tego typu złożoność powstaje, gdy dla każdego elementu należy wykonać ilość operacji proporcjonalną do liczby wszystkich elementów.

0(n log2 n) Złożoność linowo - logarytmiczna Dobre algorytmy sortujące mają taką właśnie złożoność obliczeniową. Czas wykonania przyrasta dużo wolniej od wzrostu kwadratowego Tego typu złożoność powstaje, gdy zadanie dla n elementów można rozłożyć na dwa zadania zawierające po połowie elementów.

0(n!), 0(a^An) złożoność wykładnicza Bardzo pesymistyczne algorytmy, czas wykonania rośnie bardzo szybko ze wzrostem liczby elementów wejściowych, czyli znalezienie rozwiązania może zająć najszybszym komputerom cale wieki lub tysiąclecia