Wstęp
Mając już opisany i znany model maszyny Turinga, zobaczymy po co był nam on potrzebny.
Cała rzecz polega na tym, że mając jakikolwiek algorytm/zadanie obliczeniowe, musimy mieć miarę tego jak będzie ono dobre lub czy jest w ogóle sens się nad nim roztkliwiać. Załóżmy sytuację, że mamy algorytmy sortujące i je porównujemy. Pojawia się pytanie, jaką miarę przyjąć by je porównać? Czas działania? A co jeżeli jeden wykonuje się na superkomputerze o znakomitej jakości procesorze, a drugi na podrzędnym komputerku do sterowania mikrofali? A może liczba operacji? Tylko jakich operacji? Bo co jeżeli jeden komputer ma dedykowane instrukcje procesora do sortowania np. 8 liczb rosnąco, a drugi nie? Można by się doszukiwać dużo "ale", dlatego w dzisiejszym artykule opiszę na czym polega i czym są złożoności obliczeniowe algorytmu, jak je liczyć, jak porównywać, i co mówą nam one na temat jakości algorytmów względem siebie. Przedstawimy sobie czym są funkcje asymptotyczne i oparte na nich notacje, dlaczego ich używamy, do czego służą i dlaczego są tak bardzo przydatne w opisie algorytmów. Dodatkowo przedstawimy parę przykładów jak owe liczyć i dlaczego nie zawsze algorytmy o tej samej złożoności są tak samo wydajne. Zapraszam do lektury.
Złożoność obliczeniowa.
Rzecz pierwsza. Modele obliczeń.
Zadając sobie pytanie, jak powinno porównywać się wszelkiego rodzaju algorytmy, należy, jak już wcześniej wspomniałem, wybrać jakąś miarę. Całkiem rozsądnym wyborem byłoby stwierdzenie, że czas jest znakomitym kryterium, ale we wstępie już również napomknąłem o pewnych problemach, które od razu nasuwają nam się na myśl. Trzeba więc poszukać rozwiązania tych problemów.
Jako że komputery są różne, trzeba by szukać rozwiązania na tych samych urządzeniach, dokładnie z taką samą konfiguracją sprzętową. Dodatkowo należałoby upewnić się, że program który testuje nasze rozwiązanie, będzie jedynym jaki będzie pracować na owym urządzeniu, bo co jeżeli podczas pracy naszego urządzenia, jakiś inny program będzie potrzebował zrobić cokolwiek, co zaburzy czas dostępu do czegoś czego potrzebujemy, np. pamięci? Skoro jest to jedyny program to wszystkie urządzenia na komputerze sami musimy obsłużyć, co już generuje upierdliwość. Ale może gra jest warta świeczki. Teraz musimy wprowadzić jakoś dane wejściowe, trzeba je umieścić jakoś w pamięci komputera, ale co jeżeli dane do których odwołujemy się będą rozrzucone bardzo w pamięci, przez co nie będziemy trafiać w strony? Kolejna rzecz do uwzględnienia w czasie. Co jeżeli procesor będzie cachować dane, i obliczenia w zależności od danych będą generować więcej lub mniej trafień w sam cache? Trzeba by wtedy specjalnie upośledzić procesor. Teraz jako że danych była określona ilość, należy sprawdzić, jak się zachowa jak będzie ich więcej, i więcej, i więcej. Jako że pomiar będzie empiryczny trzeba by dokonywać setek prób, zastosować jakiś model budowy wyniku, liczyć jakieś średnie itd., a i tak wynik nie będzie dokładny. Na koniec po dokonaniu już masy pomiarów, dla setek ilości danych wejściowych, należałoby zbudować jakąś funkcję, żeby tych danych w nieskończoność nie skalować i tutaj użyć jakiś algorytmów próbujących taką funkcję przybliżyć dla naszych danych. Aaa, i jeszcze, a co jeżeli od samych danych zależeć będzie czas obliczeń? Kolejna wariacja do naszej zabawy?
Widzimy więc dosyć klarownie, że to nie ma najmniejszego sensu.
Najlepszym rozwiązaniem jest więc coś, co abstrahuje od tych problemów, a jednocześnie ma sens logiczny jak i matematyczny. Korzystamy więc z modeli obliczeniowych, które "symulują" urządzenie na którym będzie liczone zadanie przez nas przedstawione. Jednym z nich i najbardziej pierwotnym jest maszyna Turinga, o której już mogliście przeczytać. Modeli jest oczywiście więcej, bo wystarczy zbudować coś co będzie miarodajną abstrakcją, a najbardziej popularnymi są maszyna RAM oraz maszyna RASP, które są całkiem niewiele oddaloną abstrakcją ponad procesorem, który znamy dzisiaj, ale je opisywać będziemy w następnych artykułach, gdyż ich szczegółowy opis stanowić będzie masę treści. Są one niesamowicie przydatne dlatego, że są bardzo wdzięczne w konstruowaniu funkcji złożoności dla algorytmów pisanych w językach wysokiego poziomu takich jak C++ czy np. Java i łatwo jest przyrównać je do realnie działających procesorów.
[Offtop]
Samych złożoności jest więcej i nie muszą się wcale odnosić do algorytmów. Przykładami są np. złożoność komunikacyjna, czy złożoność obwodu, ale te nie nawiązują bezpośrednio do algorytmów, więc ich na razie poruszać nie będziemy.
Rzecz druga. Złożoność obliczeniowa - co to w ogóle jest?
Jeżeli mowa o złożoności obliczeniowej, w kontekście algorymtów, pojęcie to nie powinno występować samodzielnie, dlatego że samo w sobie określa zbiór złożoności, ten posiada je dwie: czasową i pamięciową. Z doświadczenia jednak mogę powiedzieć, że jeżeli ktoś wypowiada się o "złożoności obliczeniowej algorytmu" to należy to rozumieć jako "złożoność czasowa algorytmu". Jest to błąd i nie należy go popełniać, i ja tego robić tu nie będę, ale w literaturze można spotkać takie uproszczenie, więc jest to niejako przestroga.
Pod hasłem "złożoności" kryje się "zapotrzebowanie". Znaczy to tyle, że analizując złożoności czasowe będziemy liczyli ile czasu potrzeba (w odpowienim modelu) aby algorytm dał nam taki efekt, np. trasę, liczbę, macierz, do jakiego został użyty, a analizując złożoność pamięciową, sprawdzimy ile będzie do tego potrzebował pamięci.
Widzimy tutaj, że sama analiza algorytmu pod kątem tych dwóch kryteriów powie nam czy jest w ogóle sens rozważać jego implementację. Weźmy np. algorytm, który potrzebować będzie niesamowicie małą ilość czasu na rozwiązanie jakiegoś problemu, ale jednocześnie będzie potrzebował \(10^{80}\) bajtów pamięci. Widzimy że nie fizycznych możliwości aby taki algorytm implementować, ani nawet w rozwiązaniu naszego problemu rozważać. Jednocześnie jeżeli znajdziemy algorytm, którego złożoność czasowa jest mniejsza od innego rozważanego, a pamięciowe są rozsądnych rozmiarów w jednym i drugim, to możemy łatwo stwierdzić, który algorytm jest dla nas lepszy, czy też szybszy, czy potrzebuje mniej pamięci (szybszy np. w rozwiązaniach na wielkich serwerach, gdzie pamięć generalnie nie jest problemem, a mniejszy pamięciowo dla małych urządzeń, np. sterowników zraszaczy, gdzie mamy bardzo małą ilość zasobów).
Złożoności owe definujemy jako funkcje. Funkcje te ubieramy w notacje asymptotyczne. Dlaczego? To zaraz. Omówmy najpierw czym jest złożoność czasowa, gdzie w prosty sposób pokażemy dlaczego funkcja, od czego zależy, i dlaczego asymptotyczna.
Rzecz trzecia. Złożoność czasowa.
Nazwa owej złożoności może być delikatnie myląca, bo sugeruje, że będziemy liczyć czas wykonania, a czas, jak wiadomo jest miarą ściśle zdefiniowaną i ma nawet jednostki! Ale jako że model matematyczny nie jest fizyczny, więc czasowi nie podlega, my sekund liczyć nie będziemy. Będziemy natomiast liczyć "kroki" czy też "operacje", a ich suma da nam ostateczny wynik (poprzez dodanie odpowiednich stałych mnożników do konkretnych operacji, np. do każdej operacji mnożenia dwóch liczb dodać mnożnik razy 0.5 sekundy, możemy oczywiście policzyć, teoretycznie, czas w jakim to się wykona, jednak na modelach na których liczymy takie coś jest bezcelowe, bo nikt nie będzie wykonywał obliczeń na fizycznie zaimplementowanej maszynie Turinga czy RAM, tylko na normalnym komputerze, a tych tyle że każdą analizę trzeba by dostosowywać do konkretnego egzemplarza. Druga sprawa jest taka, że ostatecznie w wyniku działania funkcji, których będzeiemy używać, stałe te się zredukują. Ale o tym zaraz.). Suma ta jednak skalarem nie będzie. Jako że złożoność czasowa jest funkcją, to szukamy funkcji, która nam tę sumę zdefinuje w zależności od parametrów wejściowych. A czym będą owe parametry wejściowe?
Projektując algorytmy, jakiekolwiek, zakładamy dla nich najgorszy możliwy scenariusz wykonania. Dlaczego, możnaby zapytać? Ano dlatego, że jeżeli założymy najfajniejszy, lub względnie wygodny, dopasujemy jego kroki do fajnych założeń, a te generalnie nie występują często. Mając w głowie najgorszy możliwy scenariusz, przewidzimy wszystkie możliwe opcje i ścieżki, jakimi algorytm musi podążyć i jednocześnie mając w głowie wszystkie te ścieżki, będzie można ułożyć je tak, aby stanowiły najmniejszą ilość potrzebych do ukończenia zadania kroków, co przełoży się na czas działania algorytmu.
Mamy więc pierwsze założenie, najgorszy możliwy scenariusz. Teraz co ono oznacza? Np. w problemie sortowania, lista posortowana dokładnie odwrotnie niż chcemy. Ale jeżeli taka lista będzie miała 10 elementów, to takie sortowanie można nawet ręcznie zrobić i będzie bardzo szybkie. Więc jeszcze jedną rzeczą, która wpłynie nam diametralnie na planowanie działania naszego algorytmu, będzie to, że obłsugiwać będziemy ekstremalnie wielki wolumen danych, czy też wprowadzając pojęcie, bardzo <duży rozmiar>/<duża ilość> danych wejściowych. Sortowanie już \(10^{10}\) elementów na kartce nie zadziała, a czasu na próbowanie algorymtów wszelakich, żeby wybrać najlepszy, może nam nie starczyć, więc warto wiedzieć na wstępie czy warto algorytmu użyć. Parametrem wejściowym więc będzie dla nas rozmiar danych wejściowych i będziemy go oznaczać jako \(n\). Oczywiście parametrów wejściowych, reprezentujących rozmiar, może być więcej niż jeden, np. w problemie przeszukiwania w głąb grafu (depth-first search), w którym wielkość grafu definiuje się przez ilość wierzchołków \(V\)("\(V\)ertices") oraz ilość krawędzi \(E\)("\(E\)dges"). (Przykładowa złożoność będzie wynosić \(O(V + E)\), a nie np. \(O(n)\)). Wszystko zależy od specifiki problemu, jednak zawsze sprowadzi się to do rozmiaru danych wejściowych.
Spróbujmy przeprowadzić przykład. Weźmy sobie za model jednotaśmową, deterministyczną maszynę Turinga i postarajmy się obliczyć ile zajmie jej posortowanie kolekcji liczb rosnąco, metodą bąbelkową. Sortowanie bąbelkowe polega na tym, że porównujemy sąsiadujące ze sobą elementy zaczynając od pierwszego, a kończąc na przedostatnim (Pierwszy z drugim, drugi z trzecim, trzeci z czwartym, ..., przedostatni z ostatnim), w następnym przejściu na przedostanim \(- \space1\), następnie przedostatnim\(-\space 2\) itd., aż zostanie nam jeden element. Jeżeli porównanie wykaże że elementy są mniejsze/większe w zależności od kierunku sortowania, elementy zamienia się miejscami. Listę przechodzimy tyle razy, aż nie zostanie nam tylko jeden element do sprawdzenia.
Na potrzeby uproszczenia przykładu przyjmijmy, że porównanie dwóch liczb przebiega natychmiastowo i mamy je opisane jako algorytm maszyny. Dodatkowo załóżmy że mamy miejsce w pamięci na dwie liczby i zapis/odczyt do/z nich też jest natychmiastowy. Miejsce na te liczby będą nam potrzebne do porównań. Można te założenia wdrożyć jako element działania maszyny przez, np. wyrzucenie dwóch zapamiętanych liczb na koniec taśmy i tam wykonania algorytmu porównania, wprowadzi to jednak komplikację (np.w żeby porównać dwie liczby, trzeba by je zakodować. np dziesiętnie, i rozbić je na pojedyńcze cyfry jako osobne "kwadraty" na taśmie), która nic nie wniesie, a nie o to chodzi mi w przykładzie.
A więc, na taśmę wrzucamy \(n\) liczb.
- Głowica zaczyna na pierwszej z nich, skanuje do pamięci, wjeżdza na drugą, skanuje do pamięci
- Wykonuje porównanie
- Jeżeli porównanie wykaże, że należy przestawić, przestawia
- Jest na drugiej, skanuje do pamięci, wjeżdża na trzecią, skanuje do pamięci
- Wykonuje porównanie
- Jeżeli porównanie wykaże, że należy przestawić, przestawia
- ...
- Jest na \(n - 1\), skanuje do pamięci, wjeżdża na \(n\), skanuje do pamięci
- Wykonuje porównanie
- Jeżeli porównanie wykaże, że należy przestawić przestawia
- Zaczyna od początku, tym razem kończąc na ostatniej \(-\space1\), przy następnym przelocie ostatniej \(-\space2\) itd. aż będziemy mieli jeden element do sprawdzenia.
Ok, mamy opisany algorytm. Żeby ułatwić jego zrozumienie, oto schemat, jak wyglądać będzie lista 10 liczb od 0 do 9, posortowana malejąco, po ukończeniu wszystkich punktów i przed rozpoczęciem skanowania od początku:
\([ 8, 7, 6, 5, 4, 3, 2, 1, 0, 9 ] \\\)
\([ 7, 6, 5, 4, 3, 2, 1, 0, 8, 9 ] \\\)
\([ 6, 5, 4, 3, 2, 1, 0, 7, 8, 9 ] \\\)
\([ 5, 4, 3, 2, 1, 0, 6, 7, 8, 9 ] \\\)
\([ 4, 3, 2, 1, 0, 5, 6, 7, 8, 9 ] \\\)
\([ 3, 2, 1, 0, 4, 5, 6, 7, 8, 9 ] \\\)
\([ 2, 1, 0, 3, 4, 5, 6, 7, 8, 9 ] \\\)
\([ 1, 0, 2, 3, 4, 5, 6, 7, 8, 9 ] \\\)
\([ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]\)
Policzmy teraz ile potrzeba "kroków" maszyny, aby owy zrealizować. Zakładamy najgorszy możliwy scenariusz, więc zakładamy że nasza lista jest posortowana dokładnie odwrotnie niż chcemy. No to do dzieła.
- Głowica zaczyna na pierwszej z nich (0 ruchów), skanuje do pamięci (1 skan), wjeżdza na drugą (1 ruch), skanuje do pamięci (1 skan)
- Wykonuje porównanie (1 porównanie)
- Jeżeli porównanie wykaże, że należy przestawić, przestawia
- 6 kroków: pobranie z pamięci jednej liczby (1 odczyt z pamięci) i zapis do drugiej komórki (1 zapis na taśmę), i pobranie drugiej (1 odczyt z pamięci) i zapis do pierwszej komórki (1 ruch, 1 zapis na taśmę). Powrót na drugą komórkę (1 ruch).
- Jeżeli porównanie wykaże, że należy przestawić, przestawia
- Jest na drugiej, skanuje do pamięci (1 skan), wjeżdża na trzecią (1 ruch), skanuje (1 skan)
- Wykonuje porównanie (1 porównanie)
- Jeżeli porównanie wykaże, że należy przestawić, przestawia (6 kroków)
- ...
- Jest na \(n - 1\), skanuje do pamięci (1 skan), wjeżdża na \(n\) (1 ruch), skanuje (1 skan)
- Wykonuje porównanie (1 porównanie)
- Jeżeli porównanie wykaże, że należy przestawić przestawia (6 kroków)
- Zaczyna od początku (\(n - 1\) ruchów by wrócić), tym razem kończąc na ostatniej \(-\space1\) (\(n - 2\) ruchów by wrócić), przy następnym przelocie ostatniej \(-\space2\)
(\(n - 3\) ruchów by wrócić) itd., aż będziemy mieli jeden element do sprawdzenia.
Mamy wszystko opisane, no to teraz rachunki.
Żeby wykonać pierwsze dwa punkty wykonujemy \(3 + 1 + 6 = 10\) kroków. Żeby następne dwa, również dziesięć. Tych dwupunktów mamy \(n -1\), czyli pierwszy przelot wykona nam \(10(n-1)\) kroków. Jako że na wejściu mamy kolekcję, która będzie posortowana odwrotnie niż chcemy, po pierwszym przelocie takiego algorytmu odnotujemy wszystkie porównania i przestawienia, więc zasadne jest dlaczego zakładamy że dodajemy tę szóstkę w liczbie kroków. Widzimy także, że liczba która była na początku, została "wyniesiona" na koniec listy. Mamy więc największą liczbę na końcu, mamy więc jedno mniej przestawienie, jeden mniej ruch i jedno mniej porównanie. Dodatkowo za każdym razem musimy wrócić na początek, za każdym razem również, będziemy mieli o jeden krok mniej (właśnie poprzez wyniesienie największej liczby na koniec, co sprawi, że nie trzeba będzie sprawdzać jej za każdym razem z innymi) tj. najpierw \(n -1\), później \(n -2\), następnie \(n -3\), aż dojdziemy do końca (czyli jednego elementu do sprawdzenia). Mamy więc dwie zmienne, które należy sprawdzić. Spróbujmy więc podjąć próbę wyznaczenia wzoru na ilość tych kroków, bez ciągłego liczenia po kolei.
- Porównania, przestawienia, skany, odczyty zapisy, na każdy przelot:
\(10(n-1) + 10(n-2) + 10(n-3) + ... 10\cdot 1 = \displaystyle\sum\limits_{k=1}^{n-1}10(k-1) = \frac{(10+10(n-1))\cdot (n-1)}{2} = \frac{10n^2 - 10n}{2} = 5n^2 - 5n\)
- Powroty na początek:
\((n - 1) + (n - 2) + (n-3) + ... + 1 = \displaystyle\sum\limits_{k=2}^{n-1}(k-1) = \frac{(1+(n-1))\cdot (n-1)}{2} = \frac{n^2 - n}{2}\)
Sumując wszystko razem otrzymujemy więc:
\(\displaystyle f(n) = \frac{10n^2 - 10n}{2} + \frac{n^2 - n}{2} = \frac{11n^2 - 11n}{2}\)
Udało się. Po ciężkich bojach doprowadziliśmy analizę do końca i uzyskaliśmy miarodajny wynik tego jak dużo wysiłku potrzeba do tego, żeby posortować maszyną Turinga (lekko zmodyfikowaną) listę liczb bąbelkowo. Mamy dokładną ilość operacji, jaką potrzebujemy żeby osiągnąć cel. Ale... czy aby na pewno jest to nam potrzebne?
Rzecz czwarta. Notacje asymptotyczne.
W rozważaniach na temat złożoności czasowej algorytmów pytaniem jest to, jak długo algorytm będzie rozwiązywał problem w zależności od tego jak dużo będzie potrzebował danych. Właśnie to "dużo" jest kluczem do istoty tego, dlaczego dokładne analizy niekoniecznie są potrzebne w każdym przypadku.
Co to znaczy dużo danych? \(10\), a może \(10^{10}\), a może \(10^{10^{10}}\)? W rzeczywistości może tak, ale w matematyce duże i małe, to pojęcia bardzo płynne i nie możemy na nich budować. My mamy nasze \(n\), sprawmy więc że będzie przydatne.
Złożoność czasowa to funkcja, a funkcja ma to do siebie, że się zachowuje. Zachowuje się tak, że rośnie, albo maleje, albo jest stała, albo lawiruje między tymi stanami wraz ze zmianiającymi się argumentami wejściowymi. My rozważamy zachowanie się funkcji od ilości danych wejściowych, a skoro te dane są niejako "fizycznie istniejące", możemy sobie naszą dziedzinę ograniczyć do liczb naturalnych (no bo jak fizycznie przekazać np. kolekcję o długości -1, albo -20, albo \(\frac{1}{4}\) elementów. Pustą listę natomiast można dostarczyć, więc 0 elementów można już jak najbardziej). Funkcje te będą zazwyczaj monotonicznie rosnące, ale założenie teoretyczne jest takie, że mogą być jakiekolwiek. Nic nam to nie zmienia, a jedynie troszkę skomplikuje definicje.
Skoro te funkcje rosnąć będą w nieskończoność, to jeżeli odpowiednio oddalimy się od wykresu, żeby taką funkcję obserwować, na tyle żeby przedział dziedziny był ogromny, np: od \(0\) do \(10^{100}\), zauważymy, że funkcja wygląda tak, jak najwyższy rząd jej wielkości, albo po prostu zauważymy, że największy rzędem współczynnik zdominował na tyle całą funkcję, że jej niższe rzędem współczynniki nie wpływają zbytnio na to jak funkcja wygląda. To jest właśnie klucz do rozumienia, czym jest i po co jest, notacja asymptotyczna.
Będąc daleko w funkcji, czyli mając ekstremalnie wielki rozmiar danych wejściowych, bardzo będzie nas instresowało jak długo będzie się wykonywać algorytm, ale jeżeli lwia część jego czasu jest zdominowana przez jakieś operacje, to głównie od niej zależeć będzie jak długo się to będzie liczyć. Weźmy na przykład nasze sortowanie bąbelkowe. Jakie znaczenie ma to, że odejmujemy \(\frac{11n}{2}\), w przypadku gdy \(n\) wynosi \(10000\)? Podniesienie do kwadratu tego \(n\)'a sprawia, że inne czynniki przestają mieć duże znaczenie, a czas rośnie na tyle diametralnie, że zaczynamy sie zastanawiać, czy jest sens w ogóle to sortować. Ma więc sens porównywanie algorytmów na poziomie "rzędu" ich złożoności. Tylko czym jest owy rząd i jak go wyznaczać?
Będziemy szukać takich funkcji, które dla odpowiednio dużych \(n\), czy też rozmiarów danych wejściowych, będą ograniczać w jakiś sposób naszą funkcję. Dlaczego można by zapytać? Ano dlatego, że jak wiemy, że skoro funkcja, która definiuje złożoność czasową jakiegoś algorytmu będzie np. ograniczona z góry jakąś inną funkcją, to znaczy, że algorytm nie wykona się wolniej niż owa funkcja która ją ogranicza. Można pójść dalej i ograniczać z dołu, wtedy będziemy wiedzieli, że nie wykona się szybciej niż owa funkcja. Można pójść jeszcze dalej i szukać 2 funkcji, które jednocześnie ograniczą nam naszą funkcję złożoności i z góry i z dołu, mając wtedy dokładny pogląd na to czego możemy się spodziewać po naszym algorytmie.
Mamy więc już pogląd na funkcję "rzędu" złożoności naszych algorytmów. Ta funkcja "rzędu" nazwana jest właśnie notacją asymptotyczną. Udało nam się już nie wprost wymienić 3 z nich, bez nazywania, po prostu idąc za intuicją. Teraz tą intuicję trzeba odrobinę ociosać nadając jej troszkę formalizmu matematycznego. Wszystkich notacji asymptotycznych jest 5 i kolejno wprowadzając jedną po drugiej ustalimy wszelkie formalizmy jakie są niezbędne do poprawnego ich opisu.
Recz piąta. Notacja \(O\).
Najbardziej popularną wśród opisujących złożoności algorytmów notacją, jest notacja tzw. Duże O. Dlaczego jest popularna i co oznacza? Do dzieła więc.
Duże O definuje nam zbiór funkcji, które ograniczają nam naszą funkcję z góry, od pewnego momentu, z dokładnością do pewnej stałej, czyli:
\(O(g(n)) = \{f(n): \textrm{istnieje takie} \space c > 0 \space \textrm{oraz istnieje takie} \space n_0,\space \textrm{że istnieje} \space c\cdot g(n) \geq f(n), \space \textrm{dla każdego} \space n \geq n_0\}\)
Czyli mówiąc po polsku. \(O(g(n))\) definuje nam zbiór funkcji. Zbiór ten zawiera wszystkie funkcje \(c\cdot g(n)\) dla pewnej dodatniej stałej \(c\), które ograniczają z góry, czy też są większe lub równe funckji \(f(n)\), od pewnego momentu jej dziedziny, czyli punktu \(n_0\). Próbując to jeszcze bardziej opisać, można by powiedzieć, że szukamy funkcji, które kształtem pokryją z góry nasze \(f(n)\), jako że możemy ją pomnożyć przez \(c\), od pewnego momentu już do końca. Wyglądać to może np. tak jak na tym obrazku:
Definicja ta pozwala nam na szukanie funkcji, która będzie odporna na zawirowania na danych, gdzie pewne kroki algorytmu mogą znacznie zmienić czas wykonania, np. dla sortowania dla zbiorów o liczności od 0 do 3, po prostu zrobi parę ifów i je pozamienia nie urchamiając przy tym całego mechanizmu algorytmu. Widać to dokładnie na obrazku, gdzie na początku nasza funkcja leci do góry, potem w dół, a potem znów do góry by już podążać ścieżką monotonnego wzrostu. Dodatkowo szukamy niejako "kształtu" funkcji, który ograniczy nam naszą. A to dlatego, że szukając "rzędów", będziemy szukać najbardziej dominujących czynników, a te zdefiniowane są jako funkcje elementarne, więc do nich będziemy równać.
Ale po co ta stała?
Ano dlatego, że skoro szukamy ograniczenia, a sam przebieg funkcji czy też "kształt" będzie ograniczał ją w daleko, daleko w dal dziedziny, to żeby wyeliminować fakt, że funkcja którą będziemy ograniczać, będzie mnożnona, przez co bardzo wzrośnie jej wartość w kolejnych punktach, my naszą też mnożymy.
Teraz. Dlaczego definujemy zbiór funkcji?
Ano dlatego, że skoro istnieje \(c\) oraz \(n_0\) takie że spełnione są warunki, to znaczy że istnieje conajmniej 1 para. A co jeżeli istnieją 3 pary? Albo 5? Mamy wtedy więcej tych funkcji, dlatego definujemy zbiór. Wedle definicji można jeszcze przecież dodać dowolnego rzędu funkcję która ogranicza naszą z góry. Ale czy każdą?
Spróbujmy przetestować tę notację, na problemy, który przedstawiliśmy wcześniej. Na naszym sortowaniu bąbelkowym. A więc mając \(\displaystyle f(n) = \frac{11n^2 - 11n}{2}\) musimy znaleźć \(O(g(n))\). A więc poszukajmy funkcji która ograniczy naszą z góry, weźmy np. \(g(n) = 2^n\). Cudownie. Teraz jakieś \(n_0\), np. \(8\). Czy dla \(8\) , \(2^n\) jest już większa niż \(f(n)\). Sprawdźmy więc:
\(\displaystyle f(8) = \frac{11\cdot 8^2 - 11\cdot 8}{2} = \frac{704 - 88}{2} = 308 \\ g(8) = 2^8 = 256 \\\)
No nie udało się. Ale! Przecież możemy tę funkcję mnożyć przez stałą \(c\), więc czemu by z tej własności nie skorzystać? Weźmy sobie \(c\), dajmy mu np. \(2\), i hyc, udało się. \(512\) jest niezaprzeczalnie większe niż \(308\), a jako że \(2^n\) wykładniczo leci w kosmos, nie trzeba już sprawdzać, czy aby na pewno dalej będzie ograniczać. Możemy więc powiedzieć z pełną odpowiedzialnością, że \(f(n) \in O(2^n)\).
No to teraz dwie sprawy. Dlaczego \(f(n)\) należy do \(O(2^n)\) i co to w ogóle oznacza? I czy ta informacja jest nam do czegoś w ogóle przydatna?
Pierwsza więc, dlaczego należy. Należy dlatego, że definicja notacji pokazuje nam że po pierwsze \(O(g(n))\) jest zbiorem, i dwa, spełnia warunki definicyjne. Czasami zdarza sie, że niektórzy piszą \(f(n) = O(2^n)\), czy też ogólnie zastępują zawieranie równością. Jest to uproszczenie, niezgodne z definicją. Można powiedzieć, że błąd, ale generalnie ludzie tak piszą dlatego należy na to uważać (jest to wygodne po prostu). Pierwsza sprawa jasna.
Druga. Czemu w ogóle zadałem to pytanie? Przecież mamy definicję notacji, znaleźliśmy wszystko dokładnie według definicji. Mamy więc dokładnie to czego potrzebowaliśmy. Odpowiadam więc sam sobie. Tak, mamy dokładnie to co w definicji. Wszystko ściśle i dokładnie, i cudownie. Problem w tym, że ta informacja nam nic nie wniosła w kontekście tego, jak czas algorytmu się zachowuje.
Aparat matematyczny, który jest zdefiniowany dla tej notacji, bo należy wiedzieć, że nie jest ona tylko stosowana w algorytmach, ale może być stosowana w dowolnej dziedzinie dla dowolnej funkcji, dla dowolnego celu, jest pewnym narzędziem, którego my używamy. Mamy w tym pewien cel. Celem jest oszacowanie jak szybko funkcja czasu wykonania będzie rosła, dlatego to co wyliczyliśmy jest bezużyteczne. Mimo tego że \(2^n\) będzie nam ograniczać funkcję z góry, to bardzo szybko wyleci w kosmos i nie będzie w ogóle adekwatna do tego, jak zachowuje się pierwotna funkcja czasu. Skoro celem jest oszacowanie tempa wzrostu, musimy znaleźć najmniejszy możliwy rząd funkcji, który będzie nam to opisywał, z dokładnością do stałych \(n_0\) i \(c\), które pozwolą nam dopasować ją, najlepiej jak to tylko możliwe.
Spróbujmy więc jeszcze raz. Sortowanie bąbelkowe. Funkcja czasu \(\displaystyle f(n) = \frac{11n^2 - 11n}{2}\) jest wielomianem. Od jedynki w górę dziedziny będzie tylko rosła, bo jej miejsca zerowe znajdują się w \(1\) i w \(0\), a my rozważamy tylko liczby naturalne, więc nie będzie ujemna (co może być oczywiste, z uwagi na to że jest to suma rzeczywistych podjętych operacji). Jako że jest funkcją kwadratową, będzie to wzrost po paraboli. Jako że jest to funkcja kwadratowa, najniższym rzędem, którym dałoby się ograniczyć tę funkcję, będzie funkcja kwadratowa. Sprawdźmy więc, \(g(n) = n^2\), znajdźmy jakieś \(n_0\) od którego możemy zacząć. Najlepiej od jedynki:
\(\displaystyle f(1) = \frac{10 - 10}{2} = 0\\ g(1) = 1\)
O czyżbyśmy trafili? Sprawdźmy dalej:
\(\displaystyle f(2) = \frac{10\cdot2^2 - 10\cdot 2}{2} = \frac{40 - 20}{2} = 10 \\ g(2) = 4\)
No nie do końca trafiliśmy. Ale jeszcze możemy mnożyć. Spróbujmy to połączyć. Widzimy, że współczynnik przy najwyższej potędze \(f(n)\) to \(8\). Spróbujmy go zdominować, tak, żebyśmy już od początku mogli ograniczyć naszą funkcję z góry. Przyjmijmy np. \(c = 256\), bo czemu nie. Teraz dla jedynki:
\(\displaystyle f(1) = \frac{10 - 10}{2} = 0\\ 256\cdot g(1) = 256\cdot 1 = 256\)
Jest sukces, teraz dla dwójki:
\(\displaystyle f(2) = \frac{10\cdot2^2 - 10\cdot 2}{2} = \frac{40 - 20}{2} = 10\\ 256\cdot g(2) = 256\cdot 4 = 1024\)
No i udało sie. Zdominowaliśmy funkcję na tyle, żeby ograniczyć ją jak chcemy. Można oczywiście szukać jeszcze dokładniej, co polecam zrobić w ramach ćwiczenia. Tutaj ważny jest wniosek jaki wyciągniemy z tego, że jesteśmy w stanie ogranicznyć naszą funkcję czasu, funkcją kwadratową. A sam on brzmi następująco:
Funkcja czasu, czy też złożoność czasowa algorytu sortowania bąbelkowego \(f(n)\), jest \(O(n^2)\), co oznacza że tempo jej wzrostu, czyli tempo wzrostu czasu potrzebnego do ukończenia algorytmu, rośnie kwadratowo względem rozmiaru danych wejściowych.
Co to nam daje tak naprawdę? Ano daje to, że bez zbędnego wchodzenia w specyfikę algorytmów, możemy powiedzieć, że jeżeli znajdziemy funkcję sortującą, której złożoność czasowa jest \(O(n)\), to wygraliśmy w życie, bo nawet dla kosmicznej ilości danych, będzie on niesamowicie bardziej szybszy od sortowania bąbelkowego, czy też funkcji o złożoności wyższych rzędów. Problem pojawia się wtedy, gdy mamy 2 algorytmy, których złożoność czasowa jest \(O(n^2)\), bądź po prostu jest identyczna. Wtedy, żeby sprawdzić już dokładnie, który jest szybszy, sięgamy do dokładnych analiz. Przykładem takich algorytmów są sortowanie bąbelkowe i sortowanie przez wstawianie.
Cudownie. Wiemy więc już po co tak funkcja jest, jak ją liczyć i do czego, i w jaki sposób jej używać. Ale. Rachunki trzeba będzie zrobić, więc żeby nie szukać za każdym razem współczynników i nie bawić się w zbytnie przeciążanie głowy, możemy skorzystać z własności notacji duże o. Sprawdźmy więc jakie to własności.
Pierwsza z nich, to redukcja do składnika największego rzędu.
Co to znaczy? Ano że jeżeli mamy np. funckję wielomianową, albo wykładniczą, składnik najwyższego rzędu szybko zdominuje całą funkcję, a tego właśnie szukamy, dlatego licząc złożoność z notacją duże o, zawsze redukujemy wszystkie mniejsze składniki niż ten najwyższego rzędu, np:
\(O(3n^3 + 12n^2 + n + 7) = O(3n^3)\)
Druga rzecz. Redukcja stałych mnożników.
Znaczy to tyle, że nieważne o ile będzie pomnożony najwyższego rzędu składnik, to zawsze możemy go zdominować, tak jak zrobiliśmy to obliczając naszą złożoność algorytmu sortowania bąbelkowego. Tak więc, możemy na spokojnie redukować stałe, np:
\(O(3n^3) = O(n^3)\)
Z powyższej wynika jeszcze np. to że możemy ignorować potęgi w logarytmach, ano dlatego że:
\(O(\log{n^{25}}) = O(25\cdot\log{n}) = O(\log{n})\).
Dodatkowo możemy zignorować podstawę logarytmu, bo konwersja z jednej bazy do drugiej, oznacza po prostu pomnożenie przez jakąś stałą, np:
\(O(\log_2{n}) = O(\frac{\log_3{n}}{\log_3{2}}) = O(\frac{1}{\log_3{2}}\cdot \log_3{n}) = O(\log_3{n})\)
pamiętać trzeba jednak, że odwrotności, czyli funckje wykładnicze, już niestety temu nie podlegają. Podstawy funkcji wykładniczych są różnych rzędów wielkości, np:
\(O(2^n) \neq O(3^n)\)
Podczas analiz bardziej złożonych algorytmów, gdzie będą używane np. zagnieżdzone inne algorytmy, natrafimy na przypadek, w którym będzie trzeba, podczas analizy złożoności dodać, lub pomnożyć, już przez istniejące miary złożoności, dlatego opiszmy jak zachowują się one na elementarnych działaniach.
Pierwsza rzecz, sumy. Jeżeli dodajemy dwie funckje w notacji duże o, po prostu bierzemy większą z nich. Z czego to wynika? Ano proszę.
\(O(n) + O(n^2) + O(n^3) = O(n + n^2 + n^3) = O(n^3)\)
Czyli bezpośrednio z właśności redukcji do rzędu najwyższego składnika. Czemu dodajemy funkcje wewnątrz, tak po prostu, wrzucając pod jedno \(O\)? Ano dlatego, że każdy ten wywodzi się od jakiegoś \(f(n)\), który jest funkcją czasu wykonania, więc jeżeli zamienimy te \(O\) na konkretne już funkcje \(f(n)\), zsumujemy je i poddamy działaniu funkcji \(O\) otrzymamy dokładnie taki sam wynik. Tak po prostu.
Przy mnożeniu mamy dokładnie taką samą sytuację:
\(O(n) \cdot O(n^2) \cdot O(n^3) = O(n \cdot n^2 \cdot n^3) = O(n^6)\)
A mnożenie już wewnątrz funkcji \(O\), wynika dokładnie z tego samego z czego wynikało podczas sumowania.
Przez stałą też można mnożyć, ale od razu się redukuje, więc można zupełnie to zignorować (oprócz zera oczywiście). Jeżeli będzie zainteresowanie na szczegółowy opis matematyczny tej funkcji, dajcie mi znać, a postaram się zrealizować osobny artykuł na ten temat.
Mamy więc omówioną najważniejszą notację, której notorycznie będziemy używać w przyszłości, jak również używać jej będą wszyscy, który projektują i opisują swoje algorytmy. Wiemy jak jej używać, jak ją wyliczać, co znaczy i dlaczego tak a nie inaczej. Ale wcześniej wspomniałem że wszystkich jest 5. Dlatego teraz, już nie tak szczegółowo, opisze całą resztę notacji asymptotycznych, jakie znaleźć można w literaturze.
Recz szósta. Notacje \(o\), \(\omega\), \(\Theta\), \(\Omega\).
Notacja \(o\)
Zacznijmy od siostry mniejszej dużego o. Przedstawiam państwu \(o\). Jedyna różnica jaka stoi pomiędzy dużym o i małym to jedna kreska. Kreska ta zjaduje się w porównaniu funkcji \(c\cdot g(n)\) i \(f(n)\). Proszę więc, o to definicja.
\(o(g(n)) = \{f(n): \textrm{istnieje takie} \space c > 0 \space \textrm{oraz istnieje takie} \space n_0,\space \textrm{że istnieje} \space c\cdot g(n) \gt f(n), \space \textrm{dla każdego} \space n \geq n_0\}\)
Ot cała filozofia. Duże o definiowało \(c\cdot g(n)\) większe bądź równe \(f(n)\), a małe o tylko większe. Jeszcze w swojej karierze nie znalazłem użycia tej notacji w opisie algorytmów, jeżeli ktoś z was się spotkał, proszę o maila.
Notacja \(\Omega\)
Ta notacja z kolei jest siostrą na opak notacji duże o, bo gdy duże o definiowało ograniczenie górne, notacja duże omega, będzie definiowała ograniczenie dolne. A definicja jej brzmi:
\(\Omega(g(n)) = \{f(n): \textrm{istnieje takie} \space c > 0 \space \textrm{oraz istnieje takie} \space n_0,\space \textrm{że istnieje} \space c\cdot g(n) \leq f(n), \space \textrm{dla każdego} \space n \geq n_0\}\)
Dostrzegamy w tytule rozdziału, że ma ona młodszą siostrę. Czy robi ona dokładnie odwrotnie na kształt małego o?
Dla poprawienia nastroju, obrazek poglądowy:
Notacja \(\omega\)
Tak! Dokładnie tak. Ta definiuje po prostu funkcję mniejszą, a nie mniejszą bądź równą. Proszzz, oto definicja.
\(\omega(g(n)) = \{f(n): \textrm{istnieje takie} \space c > 0 \space \textrm{oraz istnieje takie} \space n_0,\space \textrm{że istnieje} \space c\cdot g(n) < f(n), \space \textrm{dla każdego} \space n \geq n_0\}\)
Notacja \(\Theta\)
Najfajniejsze na koniec zostawiłem. Teraz najsilniejsza z notacji, najtrudniejsza w wyznaczeniu, ale i mówiąca najwięcej. Jest ona bezpośrednim połączeniem notacji \(O\) i notacji \(\Omega\), czyli prościej mówiąc szukamy teraz dwóch funkcji (a jednak tej samej). Jedna z nich ogranicza nam funkcję z góry, a druga z dołu, z dokładnością do stałch. Mając już w głowie to jak wyglądają poszczególne definicje, jedno spojrzenie na tę konkretną, powinno rozwiać wszystkie wątpliwości.
\(\Theta(g(n)) = \{f(n): \textrm{istnieje takie} \space c_0 > 0 \space\textrm{i} \space c_1 > 0 \space \textrm{oraz istnieje takie} \space n_0,\space \textrm{że istnieje} \space c_0\cdot g(n) \leq f(n) \leq c_1\cdot g(n), \space \textrm{dla każdego} \space n \geq n_0\}\)
Dlatego tej samej. Musimy znaleźć jedną funkcję i dwa współczynniki, które po przemnożeniu ograniczą nam naszą funkcję zarównio z dołu i góry. Tak by się to prezentowało, jakbyśmy przedstawili to na wykresie:
Recz ósma. Złożoności niedokładne.
Ten termin sam wymyśliłem. Co miałem na myśli?
Jeżeli czytać będziemy analizy algorytmów, dopatrzymy się czasami pojęć, że obliczona złożoność czasowa pesymistyczna jest ileś, a średnia jest ileś. Co to tak w ogóle znaczy?
Na początku wspomniałem, że algorytmy projektuje się tak, żeby działały wedle najgorszego możliwego scenariusza. Nadal to podtrzymuję. Ale okazuje się, że czasami można pewne algorytmy oceniać niekoniecznie po tym, jak zachowują się w najgorszych możliwych warunkach. Dlaczego?
Otóż dlatego, że najgorszy możliwy scenariusz, dokładnie jak najlepszy możliwy scenariusz, są scenariuszami skrajnymi, a skrajne scenariusze mają to do siebie, że generalnie (zależy to od specyfiki problemu, ale w większości przypadków jest tak jak powiem) występują rzadko. Znacznie częściej występują scenariusze, że tak powiem, średnie. Znaczy to mniej więcej tyle, np. na przykładzie sortowania, że w realnych zastosowaniach, np. serwisie internetowym albo programie do pisania kodu, kiedy będziemy potrzebować coś sortować, to bardzo rzadko będą to kolekcje z dokładnie odwrotnym sortowaniem, ale będą jedynie troszkę zamieszane. Zasadne więc jest, jeżeli projektujemy algorytmy sprawdzić wszystkie przypadki i oceniać je całkowicie. Dobrym przykładem jest QuickSort. Jest to algorytm sortowania o pesymistycznej złożoności czasowej \(O(n^2)\), czyli dokładnie takiej jak sortowanie bąbelkowe, jest jednocześnie szeroko stosowany. Dlaczego? Ano dlatego, że jego średnia złożoność czasowa wynosi \(O(n\cdot \log{n})\), czyli o rząd wielkości mniej. Więc w większości przypadków, będzie nieziemsko lepszy niż bąbelek, a gdy już spotkają się z najgorszym przypadkiem, nie będzie różnicy w sensie złożoności obliczeniowej czasowej, więc stosować można by w teorii dowolny z nich (w praktycznej implementacji będzie szybszy niż bąbelek, żeby nie było niedomówień, dlatego w sensie złożoności).
Rzecz dziewiąta. Złożoność stała \(O(1)\).
Często opisując jakieś operacje występujące w algorytmie, będziemy napotykać operacje, które nie zależą bezpośrednio od ilości wprowadzonych danych. Będziemy mówić wtedy, że ich złożoność jest stała i wynosi \(O(1)\). Jest to o tyle fajne, że np. opisanie pojedyńczej operacji dodawania, pokaże nam, że nie wpływa zbyt mocno na przebieg algorytmu, ale jednocześnie, gdy będzie w pętli, pozwoli nam wpisać ją do równania, jako jakieś \(n\cdot O(1) = O(n)\), więc algebraicznie będzie się wszystko zgadzało.
Rzecz dziesiąta. Tabela złożoności.
Wspomniałem wcześniej o rzędach złożoności. Warto wymienić te, które stosujemy najczęściej, żeby po pierwsze, szybko się ich nauczyć, a po drugie żeby wiedzieć jak je nazwać (a po trzecie, żeby ich samemu nie rozkminiać). Wspomnieliśly już wcześniej o stałej, kwadratowej i liniowej. Teraz wymieńmy już wszystkie.
- \(O(1)\) - złożoność stała
- \(O(\log{n})\) - złożoność logarytmiczna
- \(O(n)\) - złożoność liniowa
- \(O(n\cdot\log{n})\) - złożoność liniowo-logarytmiczna
- \(O(n^c)\) - złożoność wielomianowa
- \(O(c^n)\) - złożoność wykładnicza
Intuicyjnie zauważamy, że jak algorytm ma złożoność czasową wykładniczą, to czas jego wykonania szybko poleci w kosmos, wraz ze wzrostem danych, a w logarytmicznej będzie sobie delikatnie tylko wzrastał. Szukać będziemy więc rozwiązań o najniższym możliwym rzędzie złożoności.
Recz jedenasta. Złożoność pamięciowa.
Złożoność pamięciowa opisuje to, jak dużo pamięci będzie potrzebował algorytm, by zrealizować zadanie. Tak samo jak czasowa, będzie zależał od modelu w sensie dokładnym, ale w sensie rzędu będzie w większości przypadków (nie zawsze) identyczny. Pamiętamy jeszcze analizę naszego sortowania bąbelkowego? Jeżeli tak, to pamiętamy, że musieliśmy zapamiętać, oprócz samych danych wejściowych na taśmie, 2 zmienne. Teraz w zależności od podejścia możemy stwierdzić, czy pamiętanie danych wejściowych liczy się do liczenia naszej złożoności, czy nie? Jeżeli nie, to złożoność pamięciowa naszego algorytmu wyniesie \(O(2)\), czyli z pominięciem stałych czynników będzie to \(O(1)\), a jeżeli tak to \(O(n + 2)\), czyli \(O(n)\).
Nic mądrego się tutaj nie dzieje. Własności są dokładnie takie same, powody również.
Podsumowanie.
Ło matko. Dotarliśmy. Temat na pierwszy rzut oka trudny, okazał się nieziemsko łatwy. Teraz mając podstawy tego jak mierzyć jakość algorytmów względem czasu i pamięci, możemy podejść do każdego osobnego algorytmu i ocenić go sami. Wiemy jak, wiemy dlaczego i umiemy to uzasadnić. Daje nam to również wiedzę, której będę używał już płynnie w następnych artykułach, dlatego jeżeli planujecie czytać dalej, warto zapamiętać co się tutaj wydarzyło.
Dziękuję za uwagę i mam nadzieję spotkamy się w następnych artykułach :)
PS. Za wszelkie uwagi zarówno piśmiennicze, jak i merytoryczne będę bardzo wdzięczny. Jeżeli coś brzmi niezrozumiale, dajcie znać, chętnie wytłumaczę bardziej, albo zredaguję treść tak, aby brzmiało zrozumiale.
Komentarze