Złożoność obliczeniowa oraz notacja Big-O w 2 minuty.

Do wkręcania śruby, zamiast śrubokręta, można użyć młotka 🔨. Śruba zamiast wkręcona, jest wbita, ale jakby nie patrzeć, jest na miejscu. Tylko, czy aby napewno to najlepszy sposób? Po takiej robocie, nikt fachowcem nas raczej nie nazwie.

Czasem rozwiązanie problemu to nie wszystko

Tak też jest w przypadku programowania. Wspomniana wcześniej śruba po części spełniała swoją rolę, ale najprawdopodobniej zniszczyliśmy jej gwint oraz możliwe, że materiał wokół, a utrzymanie (ponowne wykręcenie i wkręcenie) będzie niemożliwe. Pare analogii tu widać już na pierwszy rzut oka 💡.

Istotne jest, aby problem został rozwiązany, ale z wykorzystaniem odpowiednich narzędzi, z zachowaniem dobrych praktyk i w (możliwie) najkrótszym czasie, zużywając przy tym racjonalną ilość zasobów 🧠.

Tylko w jaki sposób porównać dwa algorytmy? Pomocna okazuje się notacja big-o, która jest niczym więcej, jak powszechnie używanym sposobem zapisu wydajności algorytmu.

Notacja Big-O

Najbardziej przydatna (dla programisty) z notacji asymptotycznych. Oznacza, najprościej mówiąc, najgorszy możliwe scenariusz wykonania implementowanego algorytmu. Zapis notacji to nic innego, jak zwykły wzór przebiegu funkcji w którym skupiamy się na największym spośród jej składników. Należy tu zrozumieć, że notacja big-o nie ma za zadanie wskazać dokładnej liczby operacji, a jedynie wartość szacunkową.

Przykładowa funkcja: 4n² + 3n + 2
Chcąc zapisać notacje big-o dla powyższego przykładu, należy:

1. Podzielić funkcje na 3 składniki: [4n², 3n, 2].
2. Usunąć stałe: [n², n].
3. Wybrać (potencjalnie) największy składnik: [n²].
4. Wynik: O(n²) 🤓.

Rzeczą która może dziwić najbardziej, jak było w moim przypadku 🤔, jest pomijanie stałych, które według mnie były bardzo istotne. Jak już wspominałem, notacja big-o jest wartością szacunkową, która za zadanie ma ilustrowanie wzrostu funkcji, a w tym przypadku wystarczy skupić się na kluczowym składniku. Dla złożoności czasowej ⏱, oznacza szybkość wzrostu czasu wykonania przy zwiększającym się zbiorze elementów, zaś dla złożoności pamięciowej 📝, tempo wzrostu ilości zajmowanego miejsca. Dodatkowo, należy pamiętać, że operujemy na pewnym poziomie abstrakcji, gdyż zakładamy, że zbiór n jest bardzo duży.

Najpowszechniejsze typy złożoności

Wykres przedstawiający najpowszechniejsze notacje big-o. Opracowany na podstawie niniejszego linku.

1. O(1) — stała,
2. O(logn) —logarytmiczna,
3. O(n) —liniowa,
4. O(nlogn) — logarytmiczna-liniowa,
5. O(n²) — kwadratowa,
6. O(n³) — sześcienna,
7. O(n!) — silnia

Podsumowanie

Za cel postawiłem sobie przedstawienie kluczowych elementów koncepcji, jaką jest notacja big-o. Poznanie oraz dobre zrozumienie, według mnie, niesamowicie przydaje się w codziennej pracy. Szczególnie odczuwalne jest to podczas optymalizacji aplikacji oraz pracy z dużymi zbiorami danych. Stay tuned 📺.