Złożoność obliczeniowa, sumy w tablicach
Testujemy szybkość algorytmów
Spróbujmy rozwiązać następujące zadanie:
"Dany jest ciąg złożony z n liczb całkowitych dodatnich. Rozstrzygnąć, ile jest jego fragmentów o sumie równej dokładnie K."
Pierwszy i oczywisty sposób: sprawdźmy wszystkie fragmenty. Przechowajmy ciąg w tablicy A[0..n-1], dla każdej pary liczb (i, j) takiej, że i<j, obliczmy sumę A[i]+...+A[j] i sprawdźmy, czy jest równa K:
int licznik = 0; // tu będziemy zliczać fragmenty o sumie K
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++) // podwójna pętla - wykona się dla każdej pary (i, j) przy i < j.
{
int suma = 0;
for (int s = i; s <= j; s++)
suma += A[s]; // teraz suma = A[i] + ... + A[j]
if (suma == K)
licznik++;
}
cout << licznik << endl;
Jeśli zastanowimy się trochę bardziej, zauważymy że wykonujemy tu bardzo dużo niepotrzebnych obliczeń. Na przykład liczymy sumę A[1] + A[2] + A[3], a chwilę później A[1] + A[2] + A[3] + A[4], sumując ją od nowa. Zróbmy zatem inaczej: ustalmy sobie na chwilę wartość i, dla której policzymy sumy A[i], A[i] + A[i+1], A[i] + A[i+1] + A[i+2], każdą następną licząc z poprzedniej:
int licznik = 0; // tu będziemy zliczać fragmenty o sumie K
for (int i = 0; i < n; i++) // dla ustalonego i
{
int suma = 0; // zacznij od zera
for (int j = i; j < n; j++)
{
suma += A[j]; // w tej chwili suma równa jest A[i] + A[i+1] + ... + A[j]
if (suma == K) // i można sprawdzić, czy jest równa K
licznik++;
}
}
cout << licznik << endl;
Jaka jest w praktyce różnica między tymi dwoma algorytmami? Sprawdźmy, najpierw dla tablicy zawierającej 100 liczb:
$ time ./program1 < 100.in
1
real 0m0.006s
user 0m0.006s
sys 0m0.000s
$ time ./program2 < 100.in
1
real 0m0.003s
user 0m0.003s
sys 0m0.000s
Zapis ten oznacza, że uruchomiliśmy najpierw program1, a potem program2 na pliku wejściowym 100.in i zmierzyliśmy czas wykonania.
Pierwszy (to był ten kod podany wyżej) wypisał wynik 1 i działał 0.006s, a drugi (kod niżej) 0.003s. Nie są to oczywiście duże różnice – wygląda na to,
że dla takiej tablicy oba algorytmy są mniej więcej równie dobre. Sprawdźmy dla tablicy 1000 liczb:
$ time ./program1 < 1000.in
14
real 0m0.629s
user 0m0.629s
sys 0m0.000s
$ time ./program2 < 1000.in
14
real 0m0.003s
user 0m0.003s
sys 0m0.000s
$
Pierwszy program – 0.6s, drugi – 0.003s. Różnica około dwudziestokrotna, ale wciąż są to niewielkie czasy. Zobaczmy teraz wynik dla 5000 liczb:
$ time ./program1 < 5000.in
81
real 1m18.866s
user 1m18.809s
sys 0m0.000s
$ time ./program2 < 5000.in
81
real 0m0.057s
user 0m0.052s
sys 0m0.004s
Szybszy program działa w 0.05s, wolniejszy – minutę i 18 sekund. Dla 20000 liczb nie doczekalibyśmy się wyniku w żadnym rozsądnym czasie.
Złożoność obliczeniowa
Widzimy, że pierwszy program działa nie tylko wolniej, ale też różnica ta pogłębia się coraz bardziej w miarę, jak rosną dane wejściowe do algorytmu. Aby sformalizować tę obserwację, należałoby policzyć, ile operacji (przekładających się na instrukcje procesora) wykonają oba programy. Liczba instrukcji wykonanych przez algorytm nazywa się złożonością obliczeniową tego właśnie algorytmu. Liczba instrukcji zależy oczywiście od danych wejściowych – typowo jest tym większa, im większe są dane. Najczęściej zakłada się, że dane mają wielkość \(n\) (czyli na przykład, są tablicą \(n\) liczb, albo \(n\)-literowym słowem), i liczy, ile najwięcej operacji algorytm może wykonać dla takich danych (nazywa się to pesymistyczną złożonością).
Liczenie wszystkich instrukcji jest jednak niewygodne – dokładna ich liczba zależy od języka programowania, kompilatora, architektury procesora i innych rzeczy, na które najczęściej nie mamy wpływu projektując algorytm. Konieczne jest zatem pewne uproszczenie: zakłada się, na przykład, że liczymy tylko operacje arytmetyczne (dodawanie, odejmowanie, mnożenie, dzielenie) oraz że każda z nich zajmuje jeden takt procesora. To tylko jeden z możliwych sposobów myślenia – moglibyśmy liczyć zamiast tego odwołania do tablicy, albo instrukcje porównania, albo rzeczywiście próbować uwzględniać wszystkie instrukcje.
W naszym wypadku zauważamy, że najczęstszą operacją jest dodawanie (suma += A[j]). Policzmy więc, ile razy dla tablicy długości \(n\) wykona się ta instrukcja i zignorujmy wszystkie pozostałe.
Oczywiście popełniamy w ten sposób pewien błąd szacowania, ale można wyczuć, że nie jest on zbyt wielki:
innych instrukcji w naszych algorytmach jest tyle samo co dodawań, albo mniej.
Zakładając że tablica A ma długość \(n\), ile tych operacji będzie?
Trochę łatwiej jest oszacować to w wypadku drugiego programu: jedna operacja
suma += A[j] przypada na jedną iterację pętli wewnętrznej.
Dla i = 0 tych iteracji będzie \(n-1\) (od j = 0 do n-1),
dla i = 1 będzie ich \(n-2\), potem \(n-3, n-4, \ldots,\) a w ostatniej iteracji – tylko jedna.
Całkowita liczba dodawań to:
Pierwszy (wolniejszy) algorytm oszacować trudniej, ale po chwili obliczeń otrzymujemy wynik:
Teraz widać różnicę – wartości tych wyrażeń dla \(n \approx 1000\) to około pół miliona w pierwszym wypadku, i około 160 milionów w drugim. Im większe \(n\), tym te różnice stają się bardziej znaczące. Przy odpowiednio dużych (a wciąż "życiowych") danych wolniejszy algorytm przestaje mieć praktyczny sens: nawet zatrudnienie do obliczeń bardzo mocnego komputera nie sprawiłoby, że mógłby rywalizować z szybszym.
Celem algorytmiki jest szukanie właśnie takich – szybszych – algorytmów. Nie dwu–, lub trzykrotnie szybszych, ale takich, które będą działać istotnie lepiej dla bardzo dużych danych.
Notacja O i \(\Theta\)
Wiemy już, że liczenie złożoności tak naprawdę ma opisywać to, co dzieje się dla dużych danych wejściowych – różnica między \(\frac{1}{2}n^2 - \frac{1}{2}n\) a \(\frac{n^3}{6} - \frac{n}{6}\) manifestuje się dopiero dla \(n\) rzędu tysięcy. Zastanówmy się, jaka byłaby różnica między \(\frac{1}{2}n^2 - \frac{1}{2}n\), a po prostu \(\frac{1}{2}n^2\)? Praktycznie żadna – dla dużych \(n\) te wartości są bardzo bliskie sobie (na przykład dla \(n = 10000\), różnica wynosi 0.01%). Dzieje się tak dlatego, że składnik \(\frac{1}{2}n\) jest bardzo mały w porównaniu z \(\frac{1}{2}n^2\).
Wygodniej jest zatem w opisie działania algorytmu pominąć takie małe składniki. Co więcej, trochę mylący jest nawet współczynnik \(\frac{1}{2}\) w \(\frac{1}{2}n^2\) – jak pamiętamy, w analizie złożoności pominęliśmy dla prostoty niektóre instrukcje. Dodatkowo to, czy algorytm będzie dwukrotnie szybszy, zależy od konkretnej implementacji i komputera, na którym zostanie uruchomiony. Mówiąc o algorytmach, chcielibyśmy się uniezależnić od warunków zewnętrznych.
Podsumowując, istotne jest to, że pierwszy z naszych algorytmów działa w czasie "mniej–więcej" \(n^3\), a drugi – \(n^2\). Z pomocą przychodzi tu matematyczny zapis zwany notacją O.
Weźmy dla przykładu wszystkie funkcje, które dają się ograniczyć przez jakąś funkcję kwadratową, takie jak jak \(n^2\), \(3n^2\), ale też \(2n^2 + n\) (która jest mniejsza niż \(3n^2\)), czy po prostu \(7n\) (która ogranicza się przez \(7n^2\)). O takich funkcjach powiemy, że są \(O(n^2)\). Bardziej formalnie:
Funkcja \(f(n)\) jest \(O(g(n))\) , jeśli istnieje taka stała C, że \(f(n) \leq C \cdot g(n)\).
W szczególności, funkcja \(\frac{n^3}{6} - \frac{n}{6}\) opisująca złożoność pierwszego algorytmu,jest \(O(n^3)\). Funkcja \(\frac{1}{2}n^2 - \frac{1}{2}n\) – złożoność drugiego algorytmu – jest \(O(n^2)\), ale również \(O(n^3)\).
Notacja O określa tylko ograniczenie górne. Dokładniejsza jest notacja \Theta, definiowana następująco:
Funkcja \(f(n)\) jest \(\Theta(g(n))\) , jeśli istnieją takie stałe B i C, że \(f(n) \leq C \cdot g(n)\) oraz \(f(n) \geq B \cdot g(n)\).
Funkcja \(\frac{n^3}{6} - \frac{n}{6}\) jest zatem \(\Theta(n^3)\) i nie jest \(\Theta(n^2)\). Funkcja \(\frac{1}{2}n^2 - \frac{1}{2}n\) jest \(\Theta(n^2)\) i nie jest \(\Theta(n^3)\).
Algorytmy działające w złożoności \(\Theta(n)\) nazywa się często liniowymi, \(\Theta(n^2)\) – kwadratowymi, a \(\Theta(n^3)\) – sześciennymi. Bardzo często spotyka się algorytmy działające w złożoności \(\Theta(n \log n)\) (poznamy takie np. w rozdziale o sortowaniu). Bywają też algorytmy wykładnicze, działające w czasie \(\Theta(2^n)\), \(\Theta(3^n)\), lub podobnym.
Gąsienica
Nasze pierwotne zadanie, o liczeniu fragmentów ciągu o zadanej sumie, da się rozwiązać w czasie liniowym – skonstruować algorytm, który dla
\(n\)-elementowej tablicy będzie miał złożoność \(O(n)\).
Podobnie jak w kwadratowym algorytmie, dla każdego i będziemy chcieli szukać takich
j > i, dla których A[i] + ... + A[j] = K. Załóżmy więc, że dla pewnego i takie j już znaleźliśmy. Wiemy zatem, że wszystkie
większe j dadzą sumę większą niż K, nie ma więc sensu ich sprawdzać – możemy dla danego i zakończyć działanie. Jeśli teraz
zmienimy i na i+1, nie ma z kolei sensu sprawdzać "krótszych" sum – wiemy, że A[i+1] + ... + A[j] to na pewno mniej niż
K. Możemy zacząć przeszukiwanie od tego miejsca, na którym skończyliśmy uprzednio.
Jeśli dla danego i nie da się znaleźć odpowiedniego j, zatrzymujemy się na pierwszym takim, dla którego A[i] + ... + A[j] > K, i
przechodzimy z i na i+1.
int licznik = 0; // tu będziemy zliczać fragmenty o sumie K
int suma = A[0];
int j = 0;
for (int i = 0; i < n; i++) // dla ustalonego
{
while ((j < n - 1) && (suma < K))
{
j++; // zwiększaj j, doliczając A[j] do sumy
suma += A[j]; // dopóki nie przekroczysz K, albo j nie osiągnie maksymalnej wartości n-1
}
if (suma == K)
licznik++;
suma -= A[i]; // za chwilę przejdziemy od i do i+1, trzeba odliczyć A[i] od sumy
}
W tym algorytmie na pierwszy rzut oka jest podwójna pętla. Na najczęściej wykonywaną wygląda instrukcja j++ w pętli wewnętrznej. Zauważmy teraz, że
skoro j nie zwiększy się bardziej niż do n-1, ta instrukcja (jak i cała pętla wewnętrzna) po prostu nie może się w całym algorytmie wykonać
więcej niż \(n-1\) razy! To oznacza, że całkowita liczba instrukcji jest \(O(n)\).
Technika ta zwana jest (nieformalnie) gąsienicą – fragment tablicy, który składa się na sumę, na przemian ścieśnia się i rozszerza, jednocześnie przesuwając się do przodu tablicy, co przywodzi na myśl poruszanie się gąsienicy.
Sumy prefiksowe
Na zakończenie jeszcze jeden trik – jak poprzednio, mamy tablicę A[0..n-1].
Musimy obliczyć bardzo wiele sum postaci A[p] + A[p+1] + ... + A[q] dla różnych p i q.
W jaki sposób zrobić to najszybciej?
Bardzo prosto – obliczmy sobie najpierw pomocnicze sumy:
S[0] = 0
S[1] = A[0]
S[2] = A[0]+A[1]
...
S[n] = A[0]+A[1]+...+A[n-1]
Teraz widać, że A[p] + A[p+1] + ... + A[q] to S[q] - S[p-1].
Takie pomocnicze sumy nazywają się sumami prefiksowymi.
W zadaniach, w których musimy odpowiadać na pewne zapytania (tak jak tutaj o sumy na fragmentach ciągu)
często będziemy używać techniki polegającej na uprzednim
przygotowaniu pomocniczych wartości lub całych struktur danych.
Technika ta zwana jest z angielska preprocessingiem.