Złożoność obliczeniowa to prosta funkcja, która opisuje to o ile zwiększy się zapotrzebowanie na konkretny zasób, gdy zwiększy się rozmiar danych wejściowych. Tym rozmiarem danych jest np. w/w rozmiar tablicy do posortowania. Może być to również funkcja dwóch zmiennych, np. ilości wierzchołków i krawędzi w grafie. Funkcja jest zawsze niemalejąca, przy czym im wolniej rośnie, tym lepiej.
Liczą się tylko dwa zasoby: pamięć i czas procesora.
Obie złożoności oblicza się osobno, przy czym złożoność pamięciowa ma mniejszą role (w skrócie: kupno RAM/HDD jest tańsze niż. zmiana procesora i płyty głównej). Interesuje nas jak algorytm zachowa się w przypadku danych:
1. Standardowych (złożoność oczekiwana), w praktyce najważniejsza. Oznaczamy O( [tu zmienne] ), przykładowo, jeżeli mamy sortować n-elementowa tablice, to będziemy badać O(n), jeżeli mamy jakiś algorytm na grafie N-wierzchoolkowym, i M-krawedziowym, badamy O(N, M)
2. Dobrych (złożoność optymistyczna)
3. Trudnych (złożoność pesymistyczna)
Można by przypuszczać, iż jeden algorytm reagować będzie podobnie na różne dane, iż powyższe złożoności powinny być bliskie – to nieprawda.
Jak juz wspomniałem złożoność to funkcja opisująca przyrost, funkcja dość specyficzna gdyż pomijamy wszystkie stale, co może prowadzić do swoistych paradoksów. Np. załóżmy, iż mamy funkcje:
foo(dane wejściowe) {
/* Tu się cos robi na danych wejściowych */
}
i ze jej złożoność obliczeniowa jest liniowa (ten watek rozwiniemy w dalszej części), oraz iż napisaliśmy funkcje:
bar(dane_wejsciowe) {
for(i=0; i<30; i++)
foo(dane_wejsciowe);
}
Dla przykładowych danych, jeżeli funkcja foo wykonuje się 1h, to funkcja bar wykonywać się będzie 30h. Jeżeli foo wykonuje się 1min, to bar 30 min. Dla użytkownika te czasy są różne i nie postawi miedzy nimi znaku równości. Nas jednak nie interesuje bezwzględny czas wykonywania się algorytmu, ale to jak ten czas się zmienia. Zauważmy, iż jeżeli:
dla danych D1 czas wykonania foo wyniósłby 1 min, czas bar wyniósłby 1*30 = 30[min.] dla danych większych dwukrotnie od D1 czas foo wyniesie 2min, a czas bar 2*30 = 60[min.] dla danych większych trzykrotnie od D1 czas foo wyniesie 3min, a czas bar 3*30 = 90[min.]
Jak widać obie funkcje identycznie reagują na wzrost danych (tu: liniowo) i w takim kontekście należy rozumieć funkcje złożoności.
Jak wspomniałem funkcje, z których korzystamy są proste, ponadto jest ich tylko kilka (różne funkcje można przybliżyć prostszymi, na tym polega aproksymacja – termin powiązany ze złożonością). Oto one (w kolejności od najlepszej):
1. Stała. Lepiej być nie może. Wtedy nawet nie myślimy o złożoności – po prostu piszemy dalej. W teoretycznych rozważaniach zapisujemy ja jako literkę, np c, nie dbając o jej wartość.
2. logarytmiczna, taka złożoność ma np. quickort (oczekiwana), przeszukiwanie binarne, wiele operacji na drzewach, również bardzo dobrze.
3. Wielomianowa, zazwyczaj liniowa, kwadratowa, sporadycznie większa. Np. algorytmy sortowania naiwnego (BoubleSort) i naiwne wyszukiwanie wzorca w tekście.
4. Wykładnicza, wszystkie bruteforce - np. łamięce szyfry (czyli de facto algorytm rozkładu liczb na czynniki pierwsze), nawet jednak ta sytuacja nie jest beznadziejna:-]
5. Złożoność n! i hiperwykładnicza
6. Nie ma złożoności, bo nie znamy ani jednego algorytmu, który by rozwiązał dany problem, w takiej sytuacji uznalibyśmy za znakomity każdy algorytm o dowolnej złożoności.
Dwa ostatnie punkty to czysto akademickie problemy. Poznaliśmy juz teorie, pora wiec na jakiś przykład z życia wzięty.
Nasz problem jest taki, iż mamy bardzo długie liczby i chcemy je dodawać. Upraszczamy, zakładając, iż nie będzie przeniesień (np 9+1) i przepełnień(wynik nie będzie miał więcej cyfr niż indeksów w tablicy). Liczby przechowujemy w tablicy o stałej długości, tak, ze pierwszy element to pierwsza cyfra od prawej(!). Mogło by to wyglądać tak:
#define MAX 100000
long a[MAX], b[MAX], c[MAX];
/* kod czytający a i b do tablic, puste miejsce wypełniane zerami */
foo(a, b, c);
/* po wykonaniu foo() mamy c=a+b */
Zobaczmy dla paru przykładów zmienia się złożoność obliczeniowa i pamięciowa.
Najprostsze rozwiązanie to: foo(a, b, c){ for(i=0; i<MAX; i++) c[i] = a[i]+b[i]; }
Cokolwiek było by w tablicach zawsze maja one stały rozmiar, złożoność pamięciowa jest wiec stała. Można zauważyć, iż do reprezentacji cyfr nie potrzeba bardzo dużego typu, można by użyć np. short. Załóżmy, iż w naszym języku mamy typ dwubajtowy typ short, a użyty long ma 4 bajty. Nasze tablice zajmowały by w pamięci: 3*100000*2bajty = 600000 bajtów, gdy użyjemy tablicy short 3*100000*4bajty = 1200000 bajtów, gdy użyjemy tablicy long czy to jednak zmienia złożoność pamięciową? Nie, zmieniamy tylko wartość stałej, a nie typ funkcji złożoności.
Złożoność obliczeniowa również jest stała, gdyż zawartość tablicy nie wpływa na ilość obliczeń. Jest ona proporcjonalna do _stałej_ MAX. Teoretycznie złożoność jest najlepsza, jednak stale (a dokładnie stała MAX) sprawiają, iż takie cos jest nieefektywne. Możemy zaprojektować cos, co będzie się różnie zachowywać dla różnych danych, ale zawsze będzie co najmniej tak dobre jak rozwiązanie A. W czasie wpisywania wartości do tablicy możemy zapisać ilość cyfr w liczbach w zmiennych aDlugosc i bDlugosc, a następnie zmodyfikować foo()
foo(a, b, c) { dlugosc = (aDlugosc>bDlugosc) ? aDlugosc : bDlugosc; for(i=0; i<dlugosc; i++) c[i] = a[i]+b[i]; }
Teraz złożoność pamięciowa jest taka sama, natomiast ilość obliczeń zależy juz od danych(a dokładnie od ilości cyfr w liczbach). Logiczne jest, iż ilość obliczeń (u nas ilość obiegów pętli) rośne wprost proporcjonalnie do ilości cyfr, zatem złożoność obliczeniowa jest liniowa
O(n) = n
Naszym n jest większa liczba z aDlugosc, bDlugosc. Możemy pójść dalej i przeznaczyć tyle pamięci ile jest cyfr, zamiast sztywno deklarować MAX zawsze (możemy użyć kolejki), wtedy złożoność pamięciowa również jest wprost proporcjonalna do sumy ilości cyfr. Podsumowując, okazało się, iż algorytm o złożoności stałej jest gorszy od liniowego, co wydaje się dość paradoksalne. Jest to przykład na to, iż mimo, ze stale są pomijane to maja one bardzo duże znaczenie praktyczne.
