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.

Pamięciochłonność algorytmu

Oprócz czasu wykonania, drugim kluczowym aspektem oceny algorytmu jest pamięciochłonność, czyli ilość pamięci operacyjnej (RAM), jaką algorytm potrzebuje do poprawnego działania.

Każdy algorytm, poza danymi wejściowymi, wykorzystuje dodatkową pamięć na przechowywanie zmiennych, struktur danych oraz informacji pomocniczych potrzebnych w trakcie obliczeń. Analiza pamięciochłonności pozwala określić, jak bardzo "zasobożerny" jest dany algorytm pod względem pamięci.

Co składa się na zużycie pamięci?

Pamięć wykorzystywana przez algorytm nie ogranicza się tylko do danych wejściowych. Można ją podzielić na kilka elementów:

• dane wejściowe - np. tablica liczb, tekst, graf,

• zmienne pomocnicze - np. liczniki, sumy, wskaźniki,

• struktury danych tworzone w trakcie działania - np. dodatkowe tablice, stosy, kolejki,

• reprezentacja wywołań funkcji - stos wywołań (call stack).

W analizie algorytmów najczęściej interesuje nas dodatkowa pamięć, czyli ta, którą algorytm zużywa ponad dane wejściowe.

Źródło: Jakub Piskorowski

Pamięć stała i zmienna

Pod względem pamięciochłonności algorytmy można podzielić na dwie podstawowe grupy:

• Pamięć stała - Algorytm wykorzystuje stałą ilość pamięci, niezależnie od rozmiaru danych wejściowych. Oznacza to, że niezależnie czy przetwarzamy 10 czy 10 000 elementów, ilość dodatkowej pamięci pozostaje taka sama.

• Pamięć zależna od danych - Algorytm zużywa pamięć proporcjonalnie do rozmiaru danych wejściowych. Im większe dane, tym większe zapotrzebowanie na pamięć.

Dlaczego pamięciochłonność jest ważna?

W praktyce programistycznej pamięć jest zasobem ograniczonym. Nawet jeśli komputer jest szybki, może nie poradzić sobie z algorytmem, który wymaga zbyt dużej ilości pamięci.

Analiza pamięciochłonności pozwala:

• uniknąć przepełnienia pamięci (tzw. out of memory),

• projektować algorytmy działające na dużych zbiorach danych,

• porównywać rozwiązania nie tylko pod kątem szybkości, ale też zasobów.

Przykład - suma elementów tablicy

Rozważmy algorytm sumujący elementy tablicy:

suma = 0

Dla każdego elementu w tablicy:
    suma = suma + element

Wypisz suma

W tym przypadku algorytm używa:

• jednej zmiennej suma,

• zmiennej iteracyjnej (np. i),

• danych wejściowych (tablicy).

Dodatkowa pamięć nie zależy od liczby elementów tablicy.

Wniosek: pamięciochłonność jest stała.

Przykład - kopiowanie tablicy

nowa_tablica = []

Dla każdego elementu w starej_tablicy:
    dodaj element do nowa_tablica

Tutaj sytuacja wygląda inaczej. Algorytm tworzy nową strukturę danych o rozmiarze zależnym od wejścia.

Jeżeli:

• tablica ma 10 elementów -> nowa tablica ma 10 elementów,

• tablica ma 1000 elementów -> nowa tablica ma 1000 elementów.

Wniosek: pamięciochłonność rośnie liniowo wraz z rozmiarem danych.

Złożoność pamięciowa (intuicyjnie)

Tak jak w przypadku czasu wykonania, również pamięciochłonność można opisywać symbolicznie (np. O(1), O(n)), ale na tym etapie ważniejsze jest zrozumienie sensu:

• O(1) - stałe zużycie pamięci,

• O(n) - pamięć rośnie wraz z liczbą danych,

• O(n²) - pamięć rośnie bardzo szybko przy dużych danych.

Pamięciochłonność algorytmu określa, ile dodatkowej pamięci potrzebuje algorytm do wykonania obliczeń. Jest to kluczowy parametr szczególnie w przypadku dużych zbiorów danych lub systemów o ograniczonych zasobach.

Analiza pamięci pozwala świadomie decydować, czy lepiej wybrać algorytm szybszy, czy taki, który zużywa mniej pamięci – w zależności od potrzeb konkretnego problemu.

Notacja O(n)

Podczas analizy algorytmów często chcemy określić, jak zmienia się czas działania lub zużycie pamięci wraz ze wzrostem liczby danych wejściowych. Do tego celu wykorzystuje się notację O, nazywaną również notacją dużego O(ang. Big O notation).

Notacja O nie podaje dokładnego czasu działania algorytmu w sekundach. Zamiast tego opisuje tempo wzrostu liczby operacji wykonywanych przez algorytm wraz ze wzrostem rozmiaru danych wejściowych.

Dzięki temu można porównywać algorytmy niezależnie od użytego komputera czy języka programowania.

Dlaczego potrzebna jest notacja O?

Załóżmy, że dwa programy rozwiązują ten sam problem:

• pierwszy wykonuje zadanie w 0,5 sekundy na jednym komputerze,

• drugi w 0,3 sekundy na innym komputerze.

Na podstawie samego czasu trudno stwierdzić, który algorytm jest lepszy. Wynik zależy od sprzętu i warunków testu.

Notacja O pozwala skupić się na tym, jak szybko rośnie liczba operacji, gdy zwiększamy ilość danych.

Co oznacza litera n?

W notacji O symbol n oznacza rozmiar danych wejściowych.

Przykładowo:

• liczba elementów w tablicy,

• liczba znaków w tekście,

• liczba rekordów w bazie danych.

Jeżeli algorytm przetwarza 100 liczb, to n = 100. Jeżeli przetwarza 1000 liczb, to n = 1000.

Pomijanie szczegółów

W notacji O nie interesują nas dokładne liczby operacji. Liczy się jedynie tempo wzrostu.

Przykładowo:

• O(n)

• O(2n)

• O(5n)

są traktowane tak samo, ponieważ wszystkie rosną proporcjonalnie do wartości n.

Podobnie:

• O(n² + n)

• O(n² + 100)

upraszcza się do: O(n²)

ponieważ przy bardzo dużych wartościach n składnik n² ma największy wpływ na liczbę operacji.

Dlaczego notacja O jest ważna?

Notacja O pozwala:

• przewidywać zachowanie algorytmu dla dużych zbiorów danych,

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

• wybierać bardziej efektywne algorytmy,

• oceniać zarówno czas działania, jak i pamięciochłonność.

Jest to uniwersalny sposób opisu efektywności algorytmów stosowany w informatyce na całym świecie.

Przykład praktyczny

Rozważmy dwa algorytmy wyszukiwania liczby w tablicy:

Algorytm A

Sprawdza elementy jeden po drugim.

Dla każdego elementu:
    jeśli element = szukana_liczba
        zakończ

W najgorszym przypadku musi przejrzeć wszystkie elementy.

Złożoność: O(n)

Algorytm B

Porównuje każdy element z każdym innym.

Dla każdego elementu:
    dla każdego kolejnego elementu:
        wykonaj porównanie

Przy wzroście liczby danych liczba porównań rośnie bardzo szybko.

Złożoność: O(n²)

Dla małej tablicy różnica może być niewielka, ale dla tysięcy lub milionów elementów algorytm O(n) będzie znacznie szybszy.

Złożoność stała, liniowa, kwadratowa, logarytmiczna

Złożoność obliczeniowa opisuje, jak zmienia się liczba operacji wykonywanych przez algorytm w zależności od rozmiaru danych wejściowych (n). Różne algorytmy mogą rosnąć w bardzo różnym tempie - od niemal niezmiennego, aż po bardzo szybki wzrost wymagający ogromnej liczby operacji.

Złożoność stała - O(1)

Złożoność stała oznacza, że liczba operacji wykonywanych przez algorytm nie zależy od liczby danych wejściowych. Niezależnie od tego, czy przetwarzamy 10, 1000 czy 1 000 000 elementów, algorytm wykonuje zawsze podobną, stałą liczbę operacji. Typowym przykładem jest dostęp do konkretnego elementu w tablicy po indeksie.

Przykład:

element = tablica[5]

Algorytm od razu pobiera wartość z konkretnej pozycji, bez przeglądania innych elementów.

Charakterystyka:

• bardzo szybka i przewidywalna,

• najlepsza możliwa złożoność,

• wykres: linia pozioma (stała wartość).

Źródło: Jakub Piskorowski

Złożoność liniowa - O(n)

Złożoność liniowa oznacza, że liczba operacji rośnie proporcjonalnie do liczby danych wejściowych. Jeżeli liczba elementów się podwaja, liczba operacji również się podwaja.

Przykład:

suma = 0

dla każdego elementu w tablicy:
    suma = suma + element

Każdy element jest przetwarzany dokładnie jeden raz.

Charakterystyka:

• bardzo częsta w praktyce,

• wydajna dla dużych danych,

• wykres: linia rosnąca pod stałym kątem.

Źródło: Jakub Piskorowski

Złożoność kwadratowa - O(n²)

Złożoność kwadratowa oznacza, że liczba operacji rośnie proporcjonalnie do kwadratu liczby danych. W praktyce oznacza to, że każdy element jest porównywany z wieloma innymi elementami.

Przykład:

dla każdego elementu w tablicy:
    dla każdego innego elementu:
        porównaj elementy

Charakterystyka

• bardzo szybki wzrost liczby operacji,

• dobra tylko dla małych zbiorów danych,

• wykres: krzywa coraz bardziej stroma.

Przykład:

• 10 elementów -> ~100 operacji

• 100 elementów -> ~10 000 operacji

• 1000 elementów -> ~1 000 000 operacji

Źródło: Jakub Piskorowski

Złożoność logarytmiczna - O(log n)

Złożoność logarytmiczna oznacza, że liczba operacji rośnie bardzo wolno, nawet gdy dane wejściowe są duże. Najczęściej występuje w algorytmach, które dzielą problem na mniejsze części.

Przykład - wyszukiwanie binarne:

dopóki zakres nie będzie pusty:
    sprawdź środkowy element
    zawęź zakres do połowy

Każdy krok zmniejsza liczbę elementów o połowę.

Charakterystyka:

• bardzo wydajna dla dużych danych,

• typowa dla algorytmów "dziel i zwyciężaj",

• wykres: bardzo wolno rosnąca krzywa, spłaszczająca się.

Źródło: Jakub Piskorowski

Zestawienie podstawowych złożoności obliczeniowych

• Złożoność stała - O(1)

• Złożoność liniowa - O(n)

• Złożoność kwadratowa - O(n²)

• Złożoność logarytmiczna - O(log n)

Źródło: Jakub Piskorowski

Inne rodzaje złożoności obliczeniowej

Dotychczas omówione zostały cztery podstawowe rodzaje złożoności: stała O(1), liniowa O(n), kwadratowa O(n²) oraz logarytmiczna O(log n). W praktyce informatycznej można jednak spotkać również inne klasy złożoności, opisujące algorytmy o różnym tempie wzrostu liczby operacji. Poznanie ich pozwala lepiej zrozumieć, dlaczego niektóre algorytmy działają bardzo szybko nawet dla dużych zbiorów danych, podczas gdy inne stają się niepraktyczne już przy stosunkowo niewielkich wartościach n. Poniżej przedstawiono najważniejsze dodatkowe rodzaje złożoności, które często pojawiają się podczas analizy algorytmów.

• Złożoność liniowo-logarytmiczna - O(n log n)

• Złożoność sześcienna - O(n³)

• Złożoność wykładnicza - O(2ⁿ)

• Złożoność silniowa - O(n!)

• Złożoność pierwiastkowa - O(√n)

Złożoność liniowo-logarytmiczna - O(n log n)

To jedna z najważniejszych klas w praktyce informatycznej.

Występuje w algorytmach, które:

• dzielą dane na części (log n),

• ale każdą część muszą jeszcze liniowo przetworzyć (n).

Przykłady:

• sortowanie przez scalanie (Merge Sort),

• szybkie sortowanie (Quick Sort - średnio).

Charakterystyka:

• bardzo wydajna dla dużych danych,

• "złoty standard" sortowania.

Źródło: Jakub Piskorowski

Złożoność sześcienna - O(n³)

Liczba operacji rośnie jak sześcian liczby danych.

Przykład - trzy zagnieżdżone pętle:

dla i:
    dla j:
        dla k:
            operacja

Charakterystyka:

• bardzo wolna dla większych danych,

• stosowana głównie w prostych lub macierzowych obliczeniach.

Źródło: Jakub Piskorowski

Złożoność wykładnicza - O(2ⁿ)

To jedna z najbardziej kosztownych złożoności. Każdy dodatkowy element podwaja liczbę operacji.

Przykłady:

• problem plecakowy (naiwne rozwiązanie),

• generowanie wszystkich podzbiorów.

Charakterystyka:

• bardzo szybki wzrost,

• praktycznie nieużywana dla dużych n.

Źródło: Jakub Piskorowski

Złożoność silniowa - O(n!)

Jeszcze bardziej ekstremalna niż wykładnicza.

Przykład:

• problem komiwojażera (brute force),

• generowanie wszystkich permutacji.

Charakterystyka:

• ekstremalnie wolna,

• nawet dla małych n (np. 15-20) staje się niepraktyczna.

Źródło: Jakub Piskorowski

Złożoność pierwiastkowa - O(√n)

Rzadsza, ale bardzo ciekawa.

Przykład: sprawdzanie liczb pierwszych metodą optymalizowaną (do √n).

Charakterystyka:

• szybsza niż O(n),

• wolniejsza niż O(log n),

• często spotykana w teorii liczb.