Zliczanie operacji za pomocą Big-O

W konkursach szybkość ma znaczenie. Zamiast mierzyć czas działania kodu, szacuje się, ile kroków wykonuje. To oszacowanie nazywa się jego złożonością czasową. 🚀

Big-O opisuje, jak liczba operacji rośnie wraz ze wzrostem rozmiaru wejścia n. Pomija drobne szczegóły i skupia się na dominującym trendzie.

Jeśli nakład pracy nigdy nie zależy od n, mamy O(1). Odczyt jednego elementu listy lub wykonanie jednego dodawania zawsze zajmuje tyle samo czasu.

Jedna prosta pętla po n elementach ma złożoność O(n). Podwojenie rozmiaru wejścia oznacza mniej więcej podwojenie nakładu pracy. To podstawowe narzędzie codziennej pracy.

Pętla zagnieżdżona w pętli, obie wykonujące się dla n elementów, ma złożoność O(n^2). Dla n = 1000 oznacza to milion kroków, a później wzrost jest bardzo szybki.

Gdy każdy krok zmniejsza problem o połowę, otrzymuje się O(log n). Wyszukiwanie binarne obsługuje miliard elementów w zaledwie około 30 krokach. ✨

Od najszybszego do najwolniejszego typowy rząd wygląda tak: O(1), O(log n), O(n), O(n log n), O(n^2). Im wyżej na tej liście, tym lepiej dana złożoność skaluje się wraz z danymi.

Big-O pomija stałe współczynniki, więc O(2n) to po prostu O(n). Dwa przejścia nadal rosną liniowo, dlatego mnożnik nie zmienia klasy złożoności.

Gdy składniki się sumują, liczy się tylko ten, który rośnie najszybciej. O(n^2 + n) upraszcza się do O(n^2), ponieważ wraz ze wzrostem n wartość n^2 zdecydowanie przewyższa n.

Dwie pętle wykonywane jedna po drugiej sumują się do O(n + n) = O(n). Dwie pętle zagnieżdżone mnożą się, dając O(n^2). To kształt pętli wskazuje właściwą złożoność.

W konkursach ocenia się rozwiązanie na najtrudniejszym teście, dlatego należy rozumować o przypadku najgorszym. Należy założyć, że pętla wykona się w całości, a nie że wcześniej zakończy działanie.

Można już odczytywać kod jako wzrost: O(1), O(n), O(n^2) i O(log n). Należy pomijać stałe, zachowywać największy składnik i myśleć o przypadku najgorszym. 🎯