Złożoność obliczeniowa – co to takiego?

Wielu z Was na początku swojej drogi programisty pewnie miało kiedyś zagwozdkę – po co wszyscy się tak męczą, skoro można zaimplementować sortowanie bąbelkowe? Może jest to trochę dziwny przykład, ale znakomicie obrazuje tematykę dzisiejszego wpisu. Jak pewnie się domyśliliście artykuł ten będzie poświęcony tematyce złożoności obliczeniowej oraz związanych z nią notacji „O duże”, „Omega duże” oraz „Theta”.

Fot: geralt, CC0.

Złożoność obliczeniowa

Wróćmy może do wywołanego już do tablicy sortowania bąbelkowego. Jak każdy wie, choćby z lektury mojego artykułu na temat tego algorytmu, sortowanie bąbelkowe może pochwalić się złożonością czasową rzędu O(N²). Na początek zastanówmy się więc co to w ogóle oznacza?

Tak więc, głównym celem teorii złożoności obliczeniowej jest określenie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Zasobami mogą być takie wielkości jak czas, pamięć lub liczba procesorów. Wychodząc z tej definicji na płaszczyznę „informatyczną” możemy wywnioskować, że ilość zasobów niezbędnych do wykonania algorytmu można rozumieć właśnie jako jego złożoność. W zależności od rozważanego zasobu mówimy o złożoności czasowej lub też złożoności pamięciowej.

Co więc oznacza tajemniczy zapis „złożoność czasowa O(N²)”? Aby rozwikłać tą zagadkę trzeba wyjaśnić kilka kwestii. Mianowicie jak sugeruje nazwa mówimy o złożoności czasowej. Warto w tym miejscu wyjaśnić, że pojęcia tego nie rozpatrujemy w kontekście pomiaru rzeczywistego czasu zegarowego gdyż tak naprawdę wynik taki nie będzie miał nic wspólnego z algorytmem, a wpływ na niego będą miały takie czynniki jak użyty kompilator, system operacyjny lub też procesor. Jeśli mówimy o złożoności czasowej to rozpatrujemy tutaj liczbę operacji podstawowych (dominujących) w danym algorytmie. Operacją taką może być na przykład: podstawianie, porównanie lub prosta operacja arytmetyczna. Złożoność czasowa O(N²), którą opisujemy algorytm sortowania bąbelkowo oznacza więc, że dla tablicy zawierającej n liczb zostanie (w najgorszym przypadku) wykonanych n² operacji dominujących, których wynikiem będzie posortowanie danych uzyskanych na wejściu.

W poprzednim zdaniu użyłem stwierdzenia „w najgorszym przypadku” – dlaczego tak zrobiłem? Ano dlatego, że jak wspomniałem na początku artykułu z tematem złożoności obliczeniowej związany jest również inny temat, a mianowicie pojęcie notacji.

Notacja „O duże”

Notacja „O duże” (przykładowo: O(N²)) odnosi się do ograniczenia asymptotycznego tempa wzrostu czasu wykonywania algorytmu od góry.

Przykładowo, algorytm sortowania bąbelkowego w najgorszym przypadku ma czas obliczeń rzędu O(N²). Nie oznacza to jednak, że za każdym razem czas ten będzie taki sam. Jeśli dana na wejściu tablica n elementowa będzie posortowana czas obliczeń wyniesie zaledwie O(N) (przypominam, że nie mówimy tutaj o czasie w sensie czasu zegarowego, ale liczbie operacji dominujących). Tak więc notacja „O duże” informuje nas, że czas wykonywania danego algorytmu nie jest dłuży niż O(N²) – w przypadku sortowania bąbelkowego – ale może być krótszy.

Do wyrażenia górnej granicy czasu wykonywania algorytmu wykorzystywana jest notacja „O duże”

Notacja „Omega duże”

Notacja „Omega duże” (przykładowo: Ω(N)) odnosi się ograniczenia asymptotycznego tempa wzrostu czasu wykonywania algorytmu od dołu.

Przykładowo, algorytm sortowania bąbelkowego w najlepszym przypadku ma czas obliczeń rzędu Ω(N). Nie oznacza to jednak, że za każdym razem czas ten będzie taki sam. Jeżeli dana na wejściu tablica n elementowa nie będzie posortowana czas ten wyniesie Ω(N²). Tak więc notacja „Omega duże” informuje nas, że czas wykonywania danego algorytmu nie jest krótszy niż Ω(N) – w przypadku sortowania bąbelkowego – ale może być dłuższy.

Do wyrażenia dolnej graniczy czasu wykonywania algorytmu wykorzystywana jest notacja „Omega duże”.

Notacja Theta

Notacja „Theta” (przykładowo: Θ(N²)) odnosi się do określenia asymptotycznego tempa wzrostu. Opisuje ona zachowanie wartości funkcji wraz ze wzrostem jej argumentów.

Przykładowo, algorytm sortowania bąbelkowego wykonuje różne operacje (np. operacje porównania), które to umieszczone są w pętli, przez którą przechodzimy X razy. Największa możliwa liczba wywołań tej pętli to n². Należy jednak pamiętać, że każda z operacji wywołanych przez algorytm w tej pętli, zajmuje pewien czas, a suma ich czasów daje nam wartość np. c1. Dzięki temu czas wywoływania pętli możemy określić jako n² * c1.

Gdybyśmy jednak tak zostawili sprawę, to było by to zbyt duże uproszczenie, pod uwagę musimy wziąć również dodatkowe koszta, jak inicjalizacja pętli itp. Suma takich dodatkowych kosztów to np. c2. Całkowity czas wykonywania algorytmu wynosi więc: n²* c1 + c2.

Nasze dodatkowe współczynniki (c1 oraz c2) nie dają nam jednak informacji o tempie wzrostu czasu. Do tego służy właśnie notacja „theta”. Kiedy więc zapisujemy, że czas wykonywania danego algorytmu wynosi Θ(N²), to tak naprawdę chodzi nam o to, że kiedy N osiągnie wystarczająco duże wartości to czas wykonywania (w naszym przykładzie) będzie pomiędzy funkcją n² * c1, a n² * c1 + c2 (czyli nie będzie mniejszy niż n² * c1 i nie będzie większy niż n² * c1 + c2).

Algorytmy, Notacja O duże, Notacja obliczeniowa, Notacja Omega duże, Notacja Theta, O duże, Omega duże, Programowanie, Theta, Złożoność obliczeniowa