Przez złożoność obliczeniową algorytmu rozumiemy ilość zasobów potrzebnych do jego wykonania. Zasoby to przede wszystkim czas (złożoność czasowa) oraz zużytą pamięć (złożoność pamięciowa). Jest to bardzo ważny temat podczas nauki programowania, który każdy programista powinien zrozumieć.
W trakcie nauki działania algorytmów należy zrozumieć ich złożoność.
Gdy już zapoznałeś się ze wszystkimi algorytmami opisanymi w poprzednim wpisie, może nasuwać Ci się pytanie: ”Ale po co ich aż tyle?”. Oczywiście, można założyć, iż programiści szukali w wolnej chwili nowych algorytmów, jakby istniejące nie były wystarczające, aby wymyślić wszystkie możliwe opcje sortowania tablicy na świecie. Jednak to niekoniecznie było to. Otóż każdy z opisanych przeze mnie algorytmów ma swoje pewne własności i złożoności. Dobra, teraz pewnie zadajesz sobie kolejne pytanie: ”Czym jest ta złożoność czasowa, o której gość kolejny raz pisze?”. Już śpieszę z wyjaśnieniem. Złożoność czasową mierzymy jako tendencję wzrostu ilość kosztownych operacji wykonywanych (pamięciową jako ilość zajmowanej pamięci) w zależności od wzrostu danych (najczęściej rozmiaru, chociaż czasami też rozpiętośi danych). Weźmy sobie dla przykładu Bubble Sort’a. Jaka będzie złożoność czasowa takiego programu? Łatwo dostrzec, że mamy tutaj dwie pętle przechodzące po wszystkich elementach w celu ich porównania. Zatem ilość wykonań takich pętli będzie wynosić n2, gdzie n to ilość elementów w tablicy. Zatem złożoność czasowa tego programu będzie wynosić n2. Do zapisu miary złożoności używa się O-notacji, a zatem w tym przypadku będzie to O(n2). Jak łatwo zauważyć i co pewnie część z Was już wie, Bubble Sort nie jest najlepszym i najbardziej optymalnym pomysłem, a wręcz jednym z najgorszych, ponieważ na przykład dla n=1000 będziemy zawsze potrzebować wykonać aż milion operacji porównania elementów, nawet jeśli dane będą od samego początku posortowane w całości. Zoptymalizowanie bubble sorta pozwoli nam nieznacznie poprawić wydajność dla częściowo posortowanych danych, jednak jest to nieznaczna poprawa w kontekście całego algorytmu.
Uwaga: Słowo "tendencja" jest bardzo ważne - dwa algorytmy o takiej samej złożoności niekoniecznie wykonają dokładnie tyle samo operacji dla takich samych danych. Jest to notacja asymptotyczna i powiązana ona jest z matematyczną koncepcją granicy.
Teraz nasuwa się dodatkowe pytanie, jaki wpływ mają dane początkowe na złożoności algorytmów sortujących?
Złożoność czasowa algorytmu to ilość operacji wykonywanych w zależności od danych.
Poza samym pojęciem złożoności dochodzą do tego kolejne zwroty jak pesymizm, optymizm i średnia. Brzmi strasznie, ale spokojnie - zaraz wszystko się rozjaśni. Złożoność pesymistyczna to złożoność najgorsza jaką może osiągnąć algorytm - dla najgorszego rozstawu danych. Dla przykładu posłużmy się algorytmem Insertion Sort’a. Załóżmy, że dane są poukładane w najgorszy dla nas scenariusz, czyli w odwrotnej kolejności, niż powinny być posortowane. Wybierając każdy kolejny element musimy go porównywać ze wszystkimi poprzednimi i zawsze ustawiać na początek tablicy. W ten sposób otrzymujemy złożoność rzędu O(n2) i jest to nasz przypadek pesymistyczny, zatem jest to złożoność pesymistyczna. Zobaczmy co się stanie gdy będziemy mieć od początku tablicę ułożoną: Każdy element porównujemy tylko z jego poprzednikiem, a zatem złożoność będzie rzędu O(n) i jest to nasza złożoność optymistyczna. Teraz dla porównania weźmy sobie niezoptymalizowanego Bubble Sort’a. Tam każdy element musimy zawsze porównać ze wszystkimi, więc zarówno złożoność pesymistyczna jak i optymistyczna będzie rzędu O(n2). Dla zoptymalizowanego bubble sorta złożoność optymistyczna będzie liniowa.
Złożoność algorytmu może być optymistyczna, pesymistyczna bądź średnia.
Złożoność pesymistyczną zapisuje się za pomocą O-notacji (duże O). Złożonośc optymistyczną zapisuje się za pomocą Ω-notacji (duże Omega), zaś średnią za pomocą Θ-notacji (duże Theta). Najczęsciej podawaną złożonością jest ta pesymistyczna, poniewaz to ona interesuje nas najbardziej - nasze algorytmy muszą byc przygotowane na każdą ewentualność, nie tylko na najlepszy przypadek.
Wytłumaczenie skąd biorą się złożoności wszystkich poznanych przez Ciebie w tym wpisie algorytmów mogłoby przyprawić Cię o ból głowy. Jest to materiał omawiany na studiach informatycznych i są temu poświęcone całe przedmioty, więc postanowiłem oszczędzić Ci już tej męki. Także, żeby już nie przedłużyć tak prezentuje się tabela ze złożonościami:
Nazwa | Optymistyczna | Średnia | Pesymistyczna |
Bubble Sort | Ω(n2), dla zoptymalizowanego Ω(n) | Θ(n2) | O(n2) |
Insertion Sort | Ω(n) | Θ(n2) | O(n2) |
Selection Sort | Ω(n2) | Θ(n2) | O(n2) |
Quick Sort | Ω(nlog(n)) | Θ(nlog(n)) | O(n2) |
Merge Sort | Ω(nlog(n)) | Θ(nlog(n)) | O(nlog(n)) |
Heap Sort | Ω(nlog(n)) | Θ(nlog(n)) | O(nlog(n)) |
Gdy już zechcemy napisać program sortujący tablicę i wykorzystać go na poważnie w praktyce, to raczej nie będziemy używać go dla 10 czy 100 liczb, a raczej dla tablic rzędów milionów elementów. Dla przykładu i łatwych obliczeń ustalmy sobie, że n=100. Wtedy, taki prymitywny, niezoptymalizowany Bubble Sort wykonuje aż 10000 operacji porównania, z kolei wykorzystując np. Merge Sort’a będzie ich około 664, co daje olbrzymią różnicę. Stąd płynie ważny wniosek: nie liczy się tylko czy Twój kod działa, lecz też to jak on działa. Często na maturze boimy się, czy szkolny komputer poradzi sobie z zadaniem i wpadamy w panikę, jeżeli musimy długo czekać na rozwiązanie. Szkolne komputery bez problemu sobie poradzą - o ile nie bedziemy uciekali się do operacji w stylu sortowania milionów liczb sortowaniem bąbelkowym.
Przy sortowaniu wielu elementów należy rozważyć najlepszy i najszybszy sposób.
