:~$ newsletter --subscribe
cat ~/artykuly/algorytmy/zlozonosc-obliczeniowa-co-to-takiego.md

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(N2). 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(N2)”? 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(N2), którą opisujemy algorytm sortowania bąbelkowo oznacza więc, że dla tablicy zawierającej n liczb zostanie (w najgorszym przypadku) wykonanych n2 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(N2)) 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(N2). 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ższy niż O(N2) – 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 będzie posortowana w odwrotnej kolejności, czas ten wyniesie Ω(N2). 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 granicy czasu wykonywania algorytmu wykorzystywana jest notacja „Omega duże”.

Notacja Theta

Notacja „Theta” (przykładowo: Θ(N2)) 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 n2. 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 n2 * 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: n2* 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 Θ(N2), 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ą n2 * c1, a n2 * c1 + c2 (czyli nie będzie mniejszy niż n2 * c1 i nie będzie większy niż n2 * c1 + c2).

Klasy złożoności w praktyce

Teorię notacji mamy za sobą, zbierzmy więc najczęściej spotykane klasy złożoności w jedną ściągę, od najszybszej do najwolniejszej, z przykładami algorytmów, które je reprezentują:

ZłożonośćNazwaTypowy przykładn = 1000
O(1)stałaodczyt elementu tablicy po indeksie1
O(log n)logarytmicznaszukanie binarne~10
O(n)liniowaprzejście pętlą po tablicy1 000
O(n log n)liniowo-logarytmicznasortowanie przez scalanie, quicksort~10 000
O(n²)kwadratowasortowanie bąbelkowe, dwie zagnieżdżone pętle1 000 000
O(2^n)wykładniczanaiwna rekurencja Fibonacciegoogromna
O(n!)silniasprawdzenie wszystkich permutacji (komiwojażer siłowo)astronomiczna

Ostatnia kolumna pokazuje rząd liczby operacji dla tysiąca elementów i to ona najlepiej tłumaczy, czemu „wszyscy się tak męczą” zamiast pisać sortowanie bąbelkowe: różnica między n log n a n² to przy tysiącu elementów już dwa rzędy wielkości, a przy milionie elementów pięć rzędów. Ten sam program działa sekundę albo dobę.

Jak oszacować złożoność własnego kodu?

Do codziennej pracy wystarczy kilka praktycznych reguł, które pokrywają większość przypadków:

  • Pojedyncza pętla po n elementach to O(n). Dwie pętle PO KOLEI to nadal O(n), bo stałe i mniejsze składniki w notacji pomijamy: O(2n) = O(n).
  • Pętla w pętli (każda po n) to O(n²). Trzy poziomy zagnieżdżenia to O(n³) i tak dalej.
  • Dzielenie zakresu na pół w każdym kroku (jak w szukaniu binarnym) daje O(log n).
  • Pętla po n, a w niej dzielenie na pół to O(n log n), charakterystyczne dla dobrych sortowań.
  • Liczy się najgorszy składnik: kod złożony z części O(n²) i części O(n) ma łącznie złożoność O(n²).

Szybki przykład. Ile wynosi złożoność poniższej funkcji sprawdzającej, czy tablica zawiera duplikaty?

cpp
bool maDuplikaty(int tab[], int n) {
    for (int i = 0; i < n; i++)          // n przejsc...
        for (int j = i + 1; j < n; j++)  // ...po ~n/2 porownan
            if (tab[i] == tab[j])
                return true;
    return false;
}

Dwie zagnieżdżone pętle po n elementów, więc O(n²), i nie zmienia tego fakt, że wewnętrzna robi średnio połowę obrotów, bo stałą 1/2 notacja pomija. Gdybyśmy najpierw posortowali tablicę (O(n log n)) i porównali sąsiadów (O(n)), całość zeszłaby do O(n log n). Dokładnie takie rozumowanie, czyli "czy da się taniej", jest głównym praktycznym pożytkiem z teorii złożoności.

Złożoność algorytmu to jedno z kryteriów, którymi posługuje się także architektura oprogramowania: wybór struktury danych czy sposobu komunikacji między modułami to te same kompromisy, tylko na większą skalę.

Łukasz Dudziński
Łukasz Dudziński · założyciel i autor
Pasjonat informatyki, a zwłaszcza programowania. Zwariowany maniak na tle nowych technologii oraz komputerów. W wolnych chwilach bloger... więcej-o-mnie →
ls ~/artykuly/powiazane --limit 3
komentarze --count 0
rss dla komentarzy →

// brak komentarzy — bądź pierwszy

dodaj-komentarz

Komentarze są moderowane. Podane dane przetwarzamy wyłącznie w celu publikacji komentarza (polityka prywatności).