Jak mierzy się i opisuje złożoność algorytmów?

Złożoność algorytmów jest zwykle mierzona pod względem złożoności czasowej i pamięciowej, które opisują, jak liczba operacji (czas) i używana pamięć (przestrzeń) rosną w zależności od rozmiaru danych wejściowych.

Najczęściej używaną notacją jest notacja "Big O", która pokazuje górną granicę wzrostu zużycia zasobów algorytmu przy zwiększaniu danych wejściowych. Na przykład:

• O(1) — stała złożoność, czas nie zależy od rozmiaru wejścia.
• O(n) — liniowa, czas rośnie proporcjonalnie do rozmiaru wejścia.
• O(n²) — kwadratowa, czas rośnie proporcjonalnie do kwadratu rozmiaru wejścia.

Przykład w Java do obliczania sumy elementów tablicy o złożoności liniowej O(n):

public int sum(int[] arr) {
    int total = 0;
    for (int num : arr) {
        total += num;
    }
    return total;
}

Tutaj czas wykonania zależy od długości tablicy, dlatego złożoność to — O(n). Ocena algorytmów pomaga wybierać najbardziej efektywne rozwiązania, szczególnie przy pracy z dużymi danymi.