Wstęp do złożoności obliczeniowej
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[i + 1] + ... + 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 jest równa A[i] + A[i + 1] + ... + A[j].
if (suma == K) {
licznik++;
}
}
}
cout << licznik << "\n";
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 na podstawie 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];
// Teraz suma jest równa A[i] + A[i + 1] + ... + A[j].
if (suma == K) {
// Więc można sprawdzić, czy jest równa K.
licznik++;
}
}
}
cout << licznik << "\n";
Jaka jest w praktyce różnica między tymi dwoma algorytmami? Na potrzeby kursu użyjemy do ich przetestowania poleceń systemu Linux – powiemy o nich więcej w jednym z kolejnych rozdziałów. Na razie wystarczy wiedzieć tylko, że pliki 100.in
, 1000.in
i 5000.in
zawierają odpowiednio 100, 1000 i 5000 liczb całkowitych, zaś poniższe polecenia uruchamiają nasze algorytmy (pod nazwami program1
i program2
) na danych z tych plików, oraz mierzą czas potrzebny na działanie programów.
Sprawdźmy zatem ich działanie najpierw dla tablicy 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
Pierwszy program (czyli 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 program1
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 instrukcji wykonają oba programy i porównać wyniki. To jednak okazuje się bardziej skomplikowane, niż wydaje się na pierwszy rzut oka. Po pierwsze – których instrukcji? Czy chcemy liczyć linijki kodu, czy pojedyncze operacje arytmetyczne? Nawet tutaj są różnice, bo np. dodawanie wykonuje się na ogół znacznie szybciej niż dzielenie. A może chcemy zejść na bardziej podstawowy poziom i analizować, co jest pojedynczą instrukcją dla mechanizmów wewnątrz komputera (tzw. instrukcje procesora)? Wydaje się to ,,sprawiedliwe'', ale niestety zależy od języka programowania, architektury samego komputera i innych rzeczy, którymi w kontekście algorytmu zwykle nie chcemy się zajmować.
Typowe ,,kompromisowe'' rozwiązanie to wybranie jednego rodzaju operacji, najważniejszej dla programu i skupieniu się tylko na niej – można wybrać na przykład operacje arytmetyczne (dodawanie, odejmowanie, mnożenie, dzielenie) albo tylko iteracje pętli. Oczywiście, aby ten wynik miał sens, trzeba wybrać taką instrukcję, która w programie występuje najczęściej. W naszych przykładach dobrym wyborem jest na przykład instrukcja dodawania (suma += A[j]
).
Druga ważna kwestia przy liczeniu instrukcji to dane wejściowe. W zasadzie każdy algorytm dla jednych danych będzie działał bardziej efektywnie niż dla innych – z reguły dla mniejszych działa szybciej, dla większych wolniej. Dobrym wyjściem jest skupienie się na konkretnym rozmiarze danych, czyli w naszym wypadku na wielkości wejściowej tablicy, którą oznaczamy przez \(n\). Policzmy zatem dla przykładu liczbę instrukcji dodawania (ignorując wszystkie pozostałe) w drugim z naszych programów, na początek dla tablicy mającej \(5\) elementów, czyli \(n = 5\):
- Dla
i = 0
będzie5
instrukcji dodawania (po jednej dlaj = 0, 1, 2, 3, 4
), - Dla
i = 1
będą4
instrukcje (zmiennaj
przybiera wartości1, 2, 3, 4
, każda iteracja to znowu jedno dodawanie), - Dla
i = 2
będą3
instrukcje, - Dla
i = 3
będą2
instrukcje, - Dla
i = 4
będzie1
instrukcja.
Łącznie zatem algorytm wykona \(5 + 4 + 3 + 2 + 1 = 15\) instrukcji dodawania. A jaki będzie ,,ogólny'' wynik, dla pewnego \(n\)? Bardzo podobne rozumowanie prowadzi nas do wyniku
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 i typowo jest tym większa, im większe są dane. W naszym przykładzie mieliśmy ,,szczęście'' w tym sensie, że dla każdej tablicy o długości \(n\) instrukcji byłoby tyle samo. Tak nie musi być dla każdego algorytmu, ale jeśli nie jest, ze wszystkich możliwych danych o rozmiarze \(n\) wybieramy te, które byłyby dla nas najgorsze i zmusiłyby algorytm do wykonania największej liczby instrukcji. Taką złożoność nazywa się czasem pesymistyczną złożonością.
Oszacujmy jeszcze pierwszy (wolniejszy) z naszych algorytmów. Jest to odrobinę bardziej skomplikowane, ale po chwili obliczeń otrzymujemy wynik:
Teraz można powiedzieć, skąd bierze się różnica w działaniu, wstawiając do tych wzorów wartości \(n\). Dla \(n \approx 1000\) wartości tych wyrażeń 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 algorytmem. Kluczowy tutaj jest wyraz \(n^3\) w pierwszym algorytmie i \(n^2\) w drugim. Dlatego pierwszy algorytm (i inne, które wykonują około \(n^3\) operacji dla danych wielkości \(n\)) nazywa się sześciennymi, a algorytmy wykonujące \(n^2\) operacji – kwadratowymi; dlatego też różnica między algorytmem sześciennym i kwadratowym będzie dla nas kluczowa. Z kolei algorytmy takie jak szukanie maksimum/minimum w tablicy (rozdział "Poruszanie się po tablicach"), dla tablicy wielkości \(n\) wykonują około \(n\) operacji i nazywamy je liniowymi.