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.
Przez czasową złożoność obliczeniową rozumiemy ilość czasu niezbędnego do rozwiązania problemu w zależności od liczby danych wejściowych.Złożoność czasową wyrażamy albo w jednostkach czasu, albo w liczbie operacji dominujących, które należy wykonać dla n danych, aby otrzymać rozwiązanie problemu. Operacja dominująca jest operacją, której wykonanie bezpośrednio wpływa na czas wykonania całego algorytmu. Podawanie złożoności czasowej w jednostkach czasu jest niewygodne, ponieważ wynik zależy od szybkości komputera, na którym dokonano pomiarów - trudno takie wyniki odnieść do innych komputerów, szczególnie wyposażonych w inne procesory, gdzie czas wykonania podobnych operacji może znacznie się różnić. Dlatego częściej złożoność czasową wyrażamy w liczbie operacji dominujących, gdyż każdy komputer, bez względu na swoje własności, operacje te musi wykonać. Dzięki temu wynik uniezależniamy od faktycznej szybkości komputerów.
Złożoność pamięciowa określa z kolei liczbę komórek pamięci, która będzie zajęta przez dane i wyniki pośrednie tworzone w trakcie pracy algorytmu.
Złożoność czasowa - zależność pomiędzy liczbą operacji elementarnych wykonywanych w trakcie przebiegu algorytmu a rozmiarem danych wejściowych (podawana jako funkcja rozmiaru tych danych)
np.
❘ sortowanie bąbelkowe: F( N) = ?, gdzie N jest długością listy
❘ algorytm rozwiązywania problemu wież Hanoi: F( N) = ?, gdzie N jest liczbą krążków
❘ wyznaczanie minimalnego drzewa rozpinającego: F( N,M) = ?, gdzie N jest liczbą wierzchołków a M - liczbą krawędzi w grafie (sieci połączeń )
Złożoność pamięciowa - to wielkość pamięci niezbędnej do wykonania algorytmu.
Brak komentarzy:
Prześlij komentarz