<p>Nie każdy musi być kosmonautą, niemniej warto wiedzieć że Ziemia krąży wokół Słońca a nie na odwrót. Nie każdy programista musi być asem algorytmiki mimo wszystko dobrze jest mieć chociaż podstawową wiedzę na ten temat. Zwłaszcza, że znajomość, lub chociaż umiejętność porównania algorytmów, pozwala na pisanie wydajniejszych programów (albo chociaż poczucie pisania wydajniejszych programów 🙂 ). Dzisiaj w dobie języków wysokiego poziomu, które dysponują garbage collector’ami, mają wbudowany szereg struktur danych wykraczających daleko po za proste tablice, a IDE dla nich prawie myśli za programistę wdaje się to być szczególnie cenne, bo w tym dobrobycie można łatwo zapomnieć dlaczego wybór odpowiedniej struktury, lub algorytmu, nie powinien być dyktowany przyzwyczajeniami.</p>
<p><b>Big-O notation (notacja asymptotyczna)</b></p>
<p><b></b>Podstawą, jeżeli chodzi o analizę algorytmu, jest określenie złożoności funkcji, która ten algorytm opisuje. Im bardziej złożona funkcja – której argumentem jest liczba elementów wejściowych – tym dłuższy czas wykonywania algorytmu (na standardowe potrzeby, wystarczy jeżeli będziemy mówili o czasie, ale równie dobrze, zamiast o czas, może chodzić np.. O zasoby pamięci.)Podstawowym narzędziem, które pozwala na opisanie (przynajmniej w teorii :)) złożoności algorytmu jest notacja asymptotyczna. Dzięki niej możemy szybko (oczywiście jeżeli znamy złożoność danych algorytmów) dokonać odpowiedniego wyboru :). Kolejną jej zaletą jest – jako że jest to po prostu funkcja – możliwość przedstawienia ją w postaci wykresu, co może być dla niektórych osób ułatwieniem, pozwalającym na przyspieszenie analizy.</p>
<p>Notacja asymptotyczna przedstawiana jest w takiej postaci:<b><i> O(f(n))</i></b> , gdzie <b><i>n</i></b> to liczba danych wejściowych (np.. Elementów kolekcji, które trzeba posortować). </p>
---
<p> <b> Podstawowe (najczęściej spotykane w standardowych algorytmach) złożoności(</b><i>Podane są w kolejności od najbardziej do najmniej wydajnych<b>):</b></i></p>
<p><b>O(c) gdzie c to stała:</b></p>
<img src="/static/img/blog/Oc-1.png" alt="" class=" postImage" />
<p> Algorytmy z taką złożonością to marzenie programistów. Jak widać z samego zapisu, złożoność pozostaje stała niezależnie od ilości danych wejściowych. Takie algorytmy zwykle są postrzegane jako najszybsze.</p>
<p><i>Przykład algorytmu: Pobieranie danych z tablicy. </i></p>
<p><b>O(log2n) :</b></p>
<img src="/static/img/blog/log2n.png" alt="" class=" postImage" />
<p> Algorytmy ze złożonością opisywaną przez funkcje logarytmiczne mają tym lepszą, bardziej opłacalną wydajność im zbiór danych wejściowych jest większy.</p>
<p><i>Przykład algorytmu: Wstawianie elementu do drzewa czerwono-czarnego </i> </p>
<p><b>O(n) :</b></p>
<img src="/static/img/blog/On.png" alt="" class=" postImage" />
<p> Złożoność liniowa, czyli taka, której szybkość wzrostu jest stała.</p>
<p><i>Przykład algorytmu: Wyszukiwanie elementu na stosie. </i></p>
<p><b>O(nlog2n) :</b></p>
<img src="/static/img/blog/nlog2n.png" alt="" class=" postImage" />
<p> Jest to krotność złożoności O(log2n). Wiele algorytmów sortujących można opisać tą złożonością.</p>
<p><i>Przykład algorytmu: algorytm quicksort. </i></p>
<p><b>O(n^2) :</b></p>
<img src="/static/img/blog/n^2.png" alt="" class=" postImage" />
<p> Złożoność kwadratowa. Generalnie jest zła 🙂</p>
<p><i>Przykład algorytmu: Dwie zagnieżdżone pętle for </i>🙂 </p>
---
<p>Oczywiście jest to tylko mały wycinek informacji dotyczącej notacji asymptotycznej, nie mniej jednak mam nadzieję, że komuś się przysłuży, albo może wzbudzi zainteresowanie tematem 🙂 </p>