Czas wykonania algorytmu

Każdy algorytm potrzebuje pewnej ilości czasu na wykonanie wszystkich swoich operacji. Czas wykonania algorytmu określa, jak długo algorytm będzie działał dla danych wejściowych o określonym rozmiarze. Jest to jeden z najważniejszych sposobów oceny efektywności algorytmu.

W praktyce nie analizuje się zwykle rzeczywistego czasu podawanego w sekundach czy milisekundach. Taki wynik zależy bowiem od wielu czynników, między innymi od szybkości procesora, ilości pamięci RAM czy używanego języka programowania. Zamiast tego analizuje się liczbę operacji, które algorytm musi wykonać.

Im więcej operacji wykonuje algorytm, tym więcej czasu potrzebuje na zakończenie działania.

Od czego zależy czas wykonania?

Największy wpływ na czas działania ma rozmiar danych wejściowych. Oznacza się go najczęściej literą n.

Jeżeli algorytm ma przetworzyć:

• 10 liczb, wykona niewielką liczbę operacji,

• 1000 liczb, wykona znacznie więcej operacji,

• 1 000 000 liczb, liczba operacji może być bardzo duża.

Dlatego podczas analizy sprawdza się, jak wzrasta liczba wykonywanych operacji wraz ze wzrostem wartości n.

Liczenie operacji

Podczas szacowania czasu wykonania analizuje się najważniejsze instrukcje algorytmu. Mogą to być:

• porównania wartości,

• przypisania do zmiennych,

• działania matematyczne,

• odczytywanie danych,

• wywołania funkcji.

Nie ma potrzeby liczenia każdej pojedynczej instrukcji. Najważniejsze jest określenie, jak zmienia się liczba operacji przy zwiększaniu rozmiaru danych.

Źródło: Jakub Piskorowski

Przykład

Rozważmy algorytm obliczający sumę liczb zapisanych w tablicy.

suma = 0

Dla każdej liczby w tablicy:
    suma = suma + liczba

Wypisz suma

Jeżeli tablica zawiera 5 elementów, instrukcja dodawania zostanie wykonana 5 razy a ilość wykonanych operacji w całym programie wyniesie 7.

Widzimy, że liczba operacji rośnie proporcjonalnie do liczby elementów. Im większa tablica, tym dłużej działa algorytm.

Najlepszy, średni i najgorszy przypadek

Czas działania algorytmu nie zawsze jest taki sam. Często zależy od konkretnych danych wejściowych.

Wyróżnia się trzy podstawowe przypadki:

• najlepszy przypadek - algorytm wykonuje najmniej operacji,

• średni przypadek - typowa liczba operacji dla przeciętnych danych,

• najgorszy przypadek - algorytm wykonuje najwięcej operacji.

Najczęściej analizowany jest najgorszy przypadek, ponieważ pokazuje maksymalny czas potrzebny na wykonanie algorytmu.

Dlaczego analizujemy czas wykonania?

Dla małych zbiorów danych różnice między algorytmami często są niezauważalne. Jednak przy dużej liczbie danych mogą być ogromne. Algorytm wykonujący tysiąc operacji będzie działał znacznie szybciej niż algorytm wykonujący milion operacji, nawet jeśli oba rozwiązują ten sam problem.

Dlatego analiza czasu wykonania pozwala:

• ocenić efektywność algorytmu,

• porównywać różne rozwiązania tego samego problemu,

• wybierać algorytmy, które poradzą sobie z dużą ilością danych.