Notacja Big‑O (w języku polskim spotykana również jako O-notacja) to znormalizowany sposób opisu złożoności obliczeniowej algorytmów, który pozwala określić ich wydajność. Służy ona przede wszystkim do porównywania różnych algorytmów rozwiązujących ten sam problem, ułatwiając programiście wybór najbardziej efektywnego podejścia. Inaczej mówiąc to kalkulator lenistwa programu. Im mniejsza literka n w wyniku, tym szybciej idziesz po kawę.

Dlaczego wogóle liczyć złożoność?

Wyobraź sobie dwie funkcje, które robią to samo, ale jedna kończy się zanim zdążysz mrugnąć, a druga pozwala Ci przeczytać „Władcę Pierścieni” między kolejnymi klatkami animacji. Big‑O mówi nam, do której kategorii należy kod – i pozwala uniknąć pisania tej drugiej.

Co właściwie oznacza “Big‑O”?

• Big: duże, bo patrzymy na zachowanie algorytmu przy naprawdę sporych zbiorach danych
• O: od order, czyli rzędu wielkości
• (n): liczba elementów wejściowych

W skrócie: zapis O(n) odpowiada na pytanie “jak bardzo rośnie liczba operacji, gdy rośnie liczba danych?” – bez zagłębiania się w drobiazgi typu szybkość procesora czy marka kawy. Przyczym należy pamiętać, że wyznaczany górną (największą możliwą) granicę złożoności. Przy jej obliczaniu bierze się pod uwagę scenariusz pesymistyczny, czyli najgorszą możliwą sytuację, jaka może wystąpić podczas działania algorytmu.

Najpopularniejsze rangi złożoności

Charakterystyka złożoności stałej O(c) - rozwiązanie optymalne

• Niezależność od rozmiaru danych: Najważniejszą cechą O(c) jest to, że liczba obliczeń niezbędnych do wykonania zadania pozostaje taka sama, bez względu na to, jak duży jest zbiór danych wejściowych (n)
• Stabilność wydajności: Niezależnie od tego, czy kolekcja zawiera 5, czy 5 milionów elementów, operacja o złożoności stałej zostanie wykonana w niemal identycznym czasie

O(c) w praktyce: Odczyt z ArrayList

ArrayList to flagowy przykład struktury, która wykorzystuje zalety złożoności stałej podczas operacji odczytu danych (get(int index)). Aby odczytać dane, program nie musi przeszukiwać całej listy. Zamiast tego wykonuje tylko jedno obliczenie: mnoży ilość miejsca zajmowanego w pamięci przez jedną pozycję przez numer indeksu. Wynik tego działania pozwala komputerowi od razu odczytać dane z konkretnego miejsca w pamięci. Właśnie dlatego złożoność ta jest stała – liczba operacji (jedno mnożenie i dostęp do pamięci) nie zmienia się wraz ze wzrostem liczby elementów.

O(c) w strukturze HashMapy

Choć mapy są bardziej skomplikowane niż tablice, ich konstrukcja również dąży do osiągnięcia wydajności zbliżonej do O(c). Wyszukiwanie numeru kategorii (kubełka) w HashMapie odbywa się bardzo szybko, w sposób przypominający wyszukiwanie obiektu w uporządkowanej tablicy. Przy czym należy pamiętać, że ideałem wydajnościowym dla HashMapy jest sytuacja, w której w każdym kubełku znajduje się tylko jedna wartość. W takim przypadku odnalezienie konkretnego elementu po kluczu staje się operacją o wydajności niemal stałej.

Charakterystyka złożoności logarytmicznej O(log n)

• liczba operacji nie rośnie proporcjonalnie do liczby elementów (jak w O(n)), ale znacznie wolniej. Przy każdym kroku algorytmu zbiór danych, który pozostaje do przeszukania, zostaje drastycznie zredukowany.

O(log n) w strukturze HashMap - drzewa binarne

HashMapa dzieli dane na „kubełki”, a wewnątrz tych kubełków wpisy (Entry) są zorganizowane właśnie w formie drzew binarnych, w których ma zastosowanie złożoność logarytmiczna. Dzięki temu odnalezienie konkretnego klucza wewnątrz kubełka jest bardzo szybkie, nawet jeśli znajduje się tam wiele elementów. Złożoność logarytmiczna O(logn) to otwieranie książki na samym środku i sprawdzanie, czy szukane słowo jest wcześniej, czy później, a następnie powtarzanie tego procesu z połową stron, która została, az do odnalezienia właściwego hasła.

Charakterystyka złożoności linowej O(n)

• liczba operacji niezbędnych do wykonania zadania rośnie wprost proporcjonalnie do wielkości zbioru danych wejściowych (n)

O(n) w pętlach 

Klasycznym przykładem implementacji złożoności liniowej w kodzie jest pętla for lub for-each przechodząca przez całą tablicę lub listę. Jeśli tablica liczy 2000 elementów, pętla wykona 2000 iteracji; jeśli liczba elementów wzrośnie do 4000, czas wykonania również wzrośnie dwukrotnie.

O(n) w strukturach danych (LinkedList) 

W przeciwieństwie do ArrayList, LinkedList nie pozwala na bezpośredni skok do konkretnego adresu w pamięci. Program musi „ustawić się” na pierwszym obiekcie i przechodzić kolejno przez wszystkie elementy (jak po wagonach pociągu), aż dotrze do żądanego indeksu. Aby odczytać element o indeksie 1000, program musi pokonać 1000 wcześniejszych obiektów. Powoduje to, że im większa jest lista, tym wyraźniejszy jest spadek szybkości odczytu danych.

Wyobraź sobie złożoność O(n) jako sprawdzanie biletów w pociągu. Konduktor musi podejść do każdego pasażera z osobna. Jeśli w pociągu jest 50 osób, konduktor wykona 50 kontroli. Jeśli pociąg zostanie wydłużony do 100 osób, czas pracy konduktora wzrośnie dokładnie dwukrotnie. Liczba wykonanych czynności (operacji) rośnie w linii prostej wraz z liczbą wagonów i pasażerów.

Charakterystyka złożoności kwadratowej O(n²)

• Zależność operacji: Jeśli algorytm wykonuje pętlę po i elementach pierwszej tablicy i w ramach każdego jej przebiegu wykonuje dodatkową pętlę po k elementach drugiej tablicy, łączna liczba obliczeń wynosi O(i×k). Aby uprościć zapis O(i×k), w notacji Big-O przyjmuje się, że obie wartości (i oraz k) są tak samo duże i oznacza się je wspólną niewiadomą n. Prowadzi to do zapisu O(n×n), czyli właśnie O(n2) - zgodnie z podejściem, że wyznaczany górną (największą możliwą) granicę złożoności.

O(n²) w pętlach 

Wyobraź sobie, że musisz wyłożyć podłogę kwadratowymi płytkami w pokoju o boku n metrów. Jeśli pokój ma 2 metry długości (n=2), potrzebujesz 4 płytek (2×2). Jeśli jednak powiększysz pokój tylko dwukrotnie, do 4 metrów (n=4), liczba płytek (operacji) wzrośnie aż czterokrotnie – będziesz potrzebować ich 16 (4×4). Przy złożoności kwadratowej każdy niewielki wzrost rozmiaru „boku” skutkuje gwałtownym przyrostem całkowitej pracy do wykonania.

Charakterystyka złożoności wykładniczej O(cⁿ)

• przypadku złożoności wykładniczej, liczba operacji nie rośnie liniowo ani nawet kwadratowo, lecz wykładniczo. Oznacza to, że każde dodanie kolejnego elementu do zbioru danych wejściowych może w najgorszym przypadku zwielokrotnić czas potrzebny na zakończenie obliczeń.

Wyobraź sobie złożoność wykładniczą O(cn) jako łańcuszek szczęścia (piramidę finansową). Jeśli każda osoba, która otrzyma list, musi wysłać go do dwóch kolejnych osób, to po zaledwie kilku etapach liczba wysłanych listów staje się gigantyczna. Na początku (dla małego n) praca wydaje się niewielka, ale wystarczy tylko kilka dodatkowych kroków, by liczba operacji przerosła możliwości jakiegokolwiek wykonawcy. Algorytmy wykładnicze działają na podobnej zasadzie – „puchną” w tempie, nad którym bardzo trudno zapanować.

Praktyczne zastosowanie w kolekcjach 

Notacja Big-O pozwala zrozumieć różnice techniczne między strukturami danych. Przykładowo, operacja odczytu danych z ArrayList ma złożoność O(c), ponieważ dostęp do elementu uzyskuje się poprzez jedno szybkie obliczenie adresu. W przypadku LinkedList odczyt ma złożoność O(n), gdyż program musi przejść kolejno przez wszystkie wcześniejsze obiekty w łańcuchu, co przy dużych zbiorach danych znacząco wydłuża czas pracy.

Przykład