mfranczak.pl

Złożonośc i efektywność algorytmów

———————————————————————————————
ZŁOŻONOŚĆ
———————————————————————————————

Złożoność obliczeniowa algorytmu

1. złożoność czasowa – zależność między rozmiarem a czasem wykonania algorytmu
2. złożoność pamięciowa + zależność między rozmiarem a zapotrzebowaniem algorytmu na pamięć do wykonania tego algorytmu

Rząd wielkości – szacunkowe określenie liczby przybliżające jej wartość częścią całkowitą jej logarytmu dziesiętnego. Zazwyczaj służy do porównywania wielkości, które charakteryzują się wielkoskalową zmiennością, np. w technice czy fizyce.
Przykłady:

1. Dwie liczby są tego samego rzędu, jeśli różnią się o czynnik kilka (mniej niż 10). Na przykład ludność Polski i Niemiec jest tego samego rzędu (38 i 82 mln), podczas gdy ludność Rosji i Luksemburga nie (140 mln i 490 tys.).
2. Jeśli człowiek ma 2 metry wzrostu, a mrówka 4 milimetry długości, to wzrost człowieka jest o 3 rzędy wielkości większy od długości mrówki:

Złożoność czasowa zależy od liczby operacji niezbędnych do ukończenia algorytmu. Złożoność czasową można wyrazić również w jednostkach czasu. Niestety nie jest to do końca wiarygodne ze względu na różnorodność procesorów.
Podstawową operacją przy algorytmach sortowania jest np. ilość porównań !

Przykład:

1. Algorytm wyszukiwania min w zbiorze.
   n -> ilość elementów
   n-1 -> ilość porównań
   Dla algorytmu wyszukiwania rząd ten wynosi n, zatem złożoność czasowa algorytmu to O(n), mówimy że złożoność czasowa algorytmu jest rzędu n
2. Sortowanie bąbelkowe
   n -> ilość elementów
   a(n) = (1, 2, …., n-2, n-1) -> ilość porównań tworzy ciąg arytmetyczny
   czyli,
   a(1) = 1
   a(n) = n-1
   n = n-1
   Jeśli podstawimy do wzoru, otrzymamy:
   Dla algorytmu wyszukiwania rząd ten wynosi n^2, zatem złożoność czasowa algorytmu to O(n^2), mówimy że złożoność czasowa algorytmu jest rzędu n^2

Złożoność pamięciowa algorytmu to wielkość pamięci niezbędnej do wykonania algorytmu. To wielkość pamięci zajmowanej przez wszystkie zmienne.
Złożoność obliczeniowa i pamięciowa algorytmów są ze sobą powiązane.

———————————————————————————————
EFEKTYWNOŚĆ
———————————————————————————————

Efektywność algorytmów to praktyczne zastosowanie algorytmu w programie.  Ten sam algorytm może mieć inna efektywność dla liczba całkowitych a inną dla rzeczywistych. Miara na ile wydajny jest algorytm.

Rodzaj danych wejściowych i 3 przypadki:

• optymistyczny
• średni (oczekiwany)
• pesymistyczny