Po długich namowach ze strony Dawida, postanowiłem napisać "jakiś artykuł". Nie wiedziałem w zasadzie o czym mógłbym napisać, mój wybór padł jak sami widzicie na Algorytmy. Nie chciałem pisać o czymś o czym większość rzeczy już wiem dlatego padł właśnie wybór na taki temat.. bo niczego nowego byśmy się nie nauczyli powtarzając w kółko te same rzeczy. Skoro wstęp mamy za sobą to, czym jest ten algorytm? - a komu to potrzebne?

Co to jest algorytm?

Jest to zbiór instrukcji, które opisują co zrobić na poszczególnym kroku by wykonać zadanie. Inaczej mówiąc, jest to po prostu przepis kulinarny mówiący, co po kolei trzeba wrzucić do garnka by powstał obiad. Można też powiedzieć, że to takie "szczegóły trasy" z mapy Google, mówiące nam jak mamy jechać z jednego punktu do celu, tak jak na zdjęciu poniżej. Algorytmem też jest każdy fragment kodu źródłowego - to właśnie przy kodzie najczęściej przypominamy sobie, że jest coś takiego jak algorytm, a używamy ich w takich sytuacjach może nawet nieświadomi: Szczegóły trasy w mapach Google czyli jak dojechać z jednej ulicy na drugą:

źródło: Google Maps

Można to przedstawić w postaci schematu blokowego, który pokazuje kolejne kroki algorytmu opisane przez figury geometryczne:

źródło: schemat blokowy wykonany w draw.io / opracowanie własne

Szybkość algorytmu

Zupełnie jak w "receptach" niektóre zadania mogą być szybsze niż inne, czy niektóre trasy krótsze i szybsze niż inne. - jak nie dodamy cebuli to nie stracimy 5 minut na jej obieranie. Nie inaczej jest w algorytmach - bo to przecież takie recepty. Tutaj jednak przychodzi do nas Notacja dużego O, czyli zagadnienie, którego w ogóle nie zrozumiałem w szkole, a które mówi o szybkości.

Czym jest ta notacja?! Czy możemy stworzyć jakąś analogię do rzeczy nam znanej? Oczywiście! Notacja dużego O mówi o złożonościach obliczeniowych:

• Czasowa złożoność obliczeniowa - to nic innego jak czas, w którym pokonamy jakiś dystans między punktem A, a punktem B.

• Pamięciowa złożoność obliczeniowa - to z kolei możemy potraktować jako moc silnika w aucie (Jeżeli przyjmiemy, że im wyższy silnik tym szybciej dotrzemy na miejsce).

Szybkość w notacji dużego o nie jest jednak wyrażona w czasie, a w ilości operacji do wykonania - informuje jak szybko rośnie czas wykonania algorytmu. Zobaczmy na przykładzie jak to będzie wyglądać.

Przykład na podstawie wyszukiwania binarnego i prostego

Krótkie przypomnienie, mając 100 liczb musisz zgadnąć o której w danej chwili myślę..

• Wyszukiwanie proste czyli sprawdzenie wszystkich elementów po kolei:

  Ty: 1 / Ja: Większa,

  Ty: 2 / Ja: Większa.. i tak dalej, aż wreszcie powiesz 90, a ja na to "Prawidłowa odpowiedź!"

• Wyszukiwanie binarne czyli dzielenie..

  Ty: 50 / Ja: Większa,

  Ty: 75 / Ja: Większa,

  Ty: 88 / Ja: Większa,

  Ty: 96 /Ja: Większa,

  Ty: 98 / Ja: Większa,

  Ty 99, a ja na to prawidłowa odpowiedź

Łukasz jest odpowiedzialny za funkcję, która będzie uruchamiana będzie w sklepie internetowym i szukać będzie odpowiedniego produktu - produktu, którego firma Łukasza chce sprzedać. Łukasz ma w bazie danych 100 posortowanych produktów, sprawdzenie każdego z nich, po kolei od początku do końca - bo tak działa wyszukiwanie proste, potrwa: 100ms jeżeli przyjąć, że sprawdzenie jednego produktu trwa 1ms, klient powinien więc dostać wyszukiwany produkt niemalże natychmiast. Łukasz postanowił przetestować jeszcze wyszukiwania binarnego (algorytm bazujący innym algorytmie "dziel i zwyciężaj" czyli taki, który wyznacza środek i sprawdza czy element znajduje się w przedziale od początku do połowy tablicy elementów czy od połowy do końca, następnie wybiera jedną z nich i dalej dzieli elementy na pół wybierając, jedną, aż znajdzie szukany element), wyszukiwanie to sprawdzi maksymalnie 7 elementów, bo log2(100)=7. Tak więc czas wyszukiwania binarnego wyniesie 7ms.

Jednak sklep bardzo szybko rośnie i oferuje coraz to więcej rzeczy, pracodawca Łukasza poinformował go, że niedługo zaczną oferować nawet 10 000 produktów! Dlatego Łukasz sprawdził kolejny raz jak poradzi sobie funkcja oparta o wyszukiwanie binarne dla 10 000 elementów zajęło log2 10 000 = 13 ms. Łukasz porównał sobie to wyniku z wyszukiwania prostego - "Ha! tylko 13ms dla 10 000 produktów, a wyszukiwanie proste potrzebowało, aż 100 ms dla 100 produktów." - Tylko nie zauważył jednej rzeczy, porównał czasy wykonywania algorytmów, które nie rosną w tym samym tempie - dla 10 000 elementów czas wykonania się wyszukiwania prostego będzie wynosił 10 000ms czyli 10 sekund! Klienta trafiłby szlag, gdyby strona wczytywała się 10 sekund, zrezygnowałby z zakupu zanim produkt zostałby znaleziony.

Stąd trzeba pamiętać, że czasy wykonywania się algorytmów nie rosną w tym samym tempie.

Notacja dużego O informuje o tym jak szybki jest algorytm, zakładając, że mamy listę N elementów. Wyszukiwanie proste sprawdzając po kolei każdy element wykona N operacji - w takim razie w notacji dużego O możemy wyrazić szybkość tak O(n). Notacja pozwala porównać liczbę operacji i informuje jak rośnie czas wykonania algorytmu. Natomiast wyszukiwanie binarne dla liczby n elementów musi wykonać log n operacji, zatem czas wykonywania algorytmu w notacji dużego o będzie wyrażony tak: O(log n).

Zapis notacji dużego O wygląda więc prosto, najpierw mamy O mówiące, że jest to notacja dużego O, następnie w nawiasie mamy liczbę operacji - mam nadzieje, że wszystko jest zrozumiałe do tej pory?

Czekaj, czekaj więc skąd to log n? Mianowicie każde porównanie eliminuję połowę elementów z dalszych rozważań: 1 porównanie - n/2, drugie porównanie to n/4, 3 porównanie to n/8.. i tak dalej. Wykonując to odpowiednio długo, możemy uzyskać szukany element więc to będzie n/2^i = 1 gdzie i to liczba danego porównania. A wyciągając liczbę porównań (czyli naszą liczbę operacji) z równania otrzymamy i=log2(n).

Czas najgorszego przypadku

Właśnie tym jest notacja dużego O - czasem najgorszego przypadku. Szukając osoby w książce telefonicznej używając wyszukiwania prostego, możemy mieć szczęście i znaleźć ją na pierwszej pozycji. Więc wyszukiwanie wcale nie zajęło O(n) czasu, dostaliśmy wynik już w pierwszej próbie, ale dalej czas wykonywania to nie O(1), a O(n) bo notacja dużego O opisuje najgorszy przypadek czyli taki, w której ta osoba byłaby ostatnią w książce telefonicznej, a nie pierwszą. Można to więc odczytać następująco "Algorytm więc nie będzie trwał dłużej niż O(n)".

Źródła

• Główną inspiracją jest gorąco polecana i jedna z moich ulubionych książek na ten temat - włanie tak powinny wyglądać książki dydaktyczne: Algorytmy Ilustrowany Przewodnik - Aditya Y. Bhargava