Temat niniejszego artykułu z algorytmiki: notacja dużego O (ang. big O notation). Przedstawię Ci na czym ona polega i jak interpretować wzory, na jakie natrafisz 🧠. Jeżeli już teraz głowisz się już nad samym hasłem, to wchodź, a nie pożałujesz 😊!
NOTACJA DUŻEGO O POKAŻE CI EFEKTYWNOŚĆ ALGORYTMU POD KĄTEM CZASU I PAMIĘCI
Pojęcie może budzić zdziwienie przez swoją nazwę 🙂. To jest miara efektywności algorytmu.
DO CZEGO SŁUŻY NOTACJA DUŻEGO O?
Notacja dużego O pozwala na opisanie asymptotycznego stopnia wzrostu czasu (lub komórek pamięci) względem rozmiaru danych, jakie zostaną podane algorytmowi ℹ️.
Jednym z najważniejszych czynników algorytmu jaki powinien Cię interesować, to ile czasu i pamięci będzie potrzebował na dostarczenie rozwiązania problemu ⚠️. W artykule wprowadzającym kategorię algorytmiki, napisałem że to jest również sztuka badania ich efektywności 🔍.
JAKIE CZYNNIKI ALGORYTMU POZWALA NAM PRZEDSTAWIĆ NOTACJA DUŻEGO O?
2 najbardziej podstawowe kryteria, jakie powinieneś/powinnaś uwzględnić w każdym algorytmie, to 👇:
- czas (a konkretniej, to jak szybko on rośnie zależnie od rozmiaru danych),
- pamięć (konkretniej, liczba komórek pamięci jaka rośnie zależnie od rozmiaru danych).
Nie bez znaczenia podkreślam "zależnie od rozmiaru danych". Notacja dużego O pozwala nam zmierzyć czas działania określonego algorytmu bądź ile komórek pamięci będzie potrzebował na podstawie liczby operacji do wykonania wraz z rosnącym rozmiarem danych wejściowych 😲! Tego nie mierzysz w milisekundach czy innej metryce czasowej ❌! To jest definiowane jako tempo wzrostu 📈.
NA CZYM POLEGA PRZYPADEK NAJGORSZY ALGORYTMU?
Należy podkreślić, że notacja dużego O opisuje złożoność czasową i pamięciową w przypadku najgorszym ℹ️. Przypadek najgorszy algorytmu to jest taki przypadek, w którym liczba wykonanych operacji osiągnęła maksimum opisywane przez tę notację ❗.
Przykładowo, wyszukiwanie binarne charakteryzuje się poniższą złożonością czasową (pamięciowa jest inna ⚠️!) 👇:
O(log(n))
co oznacza, że dla tablicy (lub listy) mającej 100 elementów, w najgorszym przypadku wykona się 7 iteracji celem znalezienia rozwiązania ✅:
log2(100) ≈ 7
Jednak to wcale nie znaczy, że zawsze będzie tyle 💥! Rozwiązanie może zostać znalezione już za pierwszym razem i może wystarczyć zaledwie jedna iteracja (1 < 7) 1️⃣. Mówimy wtedy o przypadku optymistycznym 😊.
JAKIE SĄ JESZCZE INNE METRYKI OPISYWANIA EFEKTYWNOŚCI ALGORYTMU?
Notacja dużego O jest tylko jedną z kilku istniejących metryk opisujących efektywność algorytmu na obu płaszczyznach (czas i pamięć), która "stoi" obok następujących notacji 👇:
- notacja "omega" (opis złożoności czasowej/pamięciowej w przypadku optymistycznym),
- notacja "theta" (opis złożoności czasowej/pamięciowej w przypadku średnim),
- notacja dużego O (opis złożoności czasowej/pamięciowej w przypadku najgorszym).
JAKIE SĄ NAJCZĘŚCIEJ WYSTĘPUJĄCE ZŁOŻONOŚCI ALGORYTMÓW W PRZYPADKU NAJGORSZYM?
Możesz natrafić na różnorakie metryki, bo każdy algorytm jest zbudowany inaczej i ma różne swoje wady oraz zalety, jednak kilka z nich można wyróżnić jako "najczęściej spotykane". Przyjrzyj się tej tabelce 👇:
| NOTACJA | ZNACZENIE | OPIS | PRZYKŁAD |
| O(1) | wzrost stały | algorytm wykonuje tylko jedną instrukcję celem znalezienia rozwiązania | pobranie elementu z tablicy po podaniu indeksu |
| O(log(n)) | wzrost logarytmiczny | algorytm w najgorszym przypadku wykonuje tylko log2(n) instrukcji celem znalezienia rozwiązania | wyszukiwanie binarne |
| O(n*log(n)) | wzrost pseudowielomianowy | algorytm w najgorszym przypadku wykonuje n*log2(n) instrukcji celem znalezienia rozwiązania | sortowanie przez scalanie |
| O(n2) | wzrost kwadratowy | algorytm w najgorszym przypadku wykonuje n2 instrukcji celem znalezienia rozwiązania | sortowanie przez wybieranie |
| O(n!) | wzrost wykładniczy | algorytm w najgorszym przypadku wykonuje aż n! ("n silnia") instrukcji celem znalezienia rozwiązania | problem komiwojażera |
Pamiętaj, że algorytm może przyjmować własne bardzo rzadko spotykane formy, jak na przykład 👇:
O(⌊√n⌋*log(n))
Podłoga z pierwiastka z N przemnożona przez logarytm z N przy podstawie 2 😅.
 |
Notacja dużego O jest matematyczną miarą tempa wzrostu złożoności obliczeniowej (czasowej) lub pamięciowej wraz z rosnącym rozmiarem danych wejściowych. Im mniejszy wzrost, tym lepiej.
Dotarliśmy do mety 😊. Notacja dużego O może być decydująca w wyborze odpowiedniego algorytmu do naszych potrzeb projektowych 💪. Trzeba jednak dobrze wgłębić się w temat z matematycznego punktu widzenia, aby w pełni zrozumieć to zagadnienie 💥.