Głębiej
Big-O to asymptotyczne ograniczenie z góry, opisujące jak rośnie zasób (czas/pamięć), gdy rośnie rozmiar wejścia.
Ważne niuanse:
- Ignoruje stałe i składniki niższego rzędu, żeby porównać skalowanie.
- Trzeba doprecyzować przypadek: worst-case, average-case, amortized.
- Big-O to górne ograniczenie; Θ to ścisłe; Ω to dolne.
Przykłady
- Sortowanie O(n log n) skaluje się dużo lepiej niż O(n^2) przy dużych n.
- Dwa algorytmy O(n) mogą różnić się mocno przez stałe i dostęp do pamięci.
Typowe pułapki
- Traktowanie Big-O jako dokładnego czasu.
- Zakładanie, że to samo Big-O = ta sama szybkość.
- Pomijanie pamięci (często to ona jest bottleneckiem).