Czym jest notacja dużego O?

Notacja Big O (Big O) to notacja matematyczna używana do opisu zachowania asymptotycznego funkcji i jej górnej granicy. W kontekście rozwoju oprogramowania jest stosowana do oceny wydajności algorytmów pod względem zużycia czasu (złożoności czasowej) i pamięci (złożoności przestrzennej) w miarę wzrostu rozmiaru danych wejściowych. Opisuje najgorszy scenariusz wykonania.

Najczęstsze klasy złożoności czasowej:

• O(1): Czas stały. Czas wykonania nie zależy od rozmiaru danych wejściowych.
• O(log n): Czas logarytmiczny. Czas wykonania rośnie powoli wraz ze wzrostem rozmiaru danych wejściowych (np. wyszukiwanie binarne).
• O(n): Czas liniowy. Czas wykonania jest proporcjonalny do rozmiaru danych wejściowych (np. liniowe przeszukiwanie).
• O(n log n): Czas liniowo-logarytmiczny. Często występuje w efektywnych algorytmach sortowania (np. szybkie sortowanie, sortowanie przez scalanie).
• O(n^2): Czas kwadratowy. Czas wykonania rośnie proporcjonalnie do kwadratu rozmiaru danych wejściowych (np. sortowanie bąbelkowe, sortowanie przez wybór).
• O(2^n): Czas wykładniczy. Czas wykonania rośnie bardzo szybko wraz ze wzrostem rozmiaru danych wejściowych. Często występuje w problemach pełnego przeszukiwania.

Przykłady kodu i ich złożoność czasowa:

// O(1)
int pierwszyElement = array[0];

// O(n)
for (int i = 0; i < array.length; i++) {
    // jakaś operacja
}

// O(n^2)
for (int i = 0; i < array.length; i++) {
    for (int j = 0; j < array.length; j++) {
        // jakaś operacja
    }
}

Notacja Big O koncentruje się na dominującym składniku wyrażenia i ignoruje stałe oraz mniej istotne składniki, ponieważ przy dużych danych ich wkład staje się nieznaczący. Na przykład algorytm o złożoności O(2n^2 + 5n + 10) jest uważany za O(n^2).

Zrozumienie Big O jest ważne przy wyborze najbardziej wydajnych algorytmów i struktur danych podczas rozwoju oprogramowania.