Jedan od važnih principa optimizacije algoritama je taj da se izbegne da računar dugotrajnim iterativnim postupkom (u linearnoj ili višoj složenosti) računa nešto što se unapred može izračunati primenom matematičkih formula (u konstantnoj složenosti).
Na primer, računanje zbira prvih \(n\) prirodnih brojeva u programu ne bi trebalo da bude linearne složenosti, već konstantne, jer se zna da je taj zbir jednak \(1 + 2 + \ldots + n = n(n+1)/2\). Slične optimizacije se mogu primeniti i kada je potrebno izračunati \(n\)-ti element ili zbir aritmetičkog ili zbir geometrijskog niza ili bilo kog drugog niza koji možemo sabrati primenom pogodne matematičke formule.
Dalje, često se dešava da nam je potrebno da izračunamo koliko ima nekih objekata. Tada se često bolje rešenje dobija primenom kombinatornih formula nego procedurom koja generiše sve takve objekte (ili, još gore, u nekom širem skupu proveravala koji od objekata zadovoljavaju tražena svojstva). Na primer, \(n\)-tocifreni brojevi koji se zapisuju samo pomoću dve različite cifre se mogu lako prebrojati primenom kombinatorike i veoma loše rešenje je da se u programu generišu i analiziraju svi \(n\)-tocifreni brojevi.
I u optimizacionim problemima je ponekad moguće jednoznačno odrediti karakterizaciju maksimalne tj. minimalne vrednosti i takva rešenja su mnogo bolja nego isprobavanje velikog broja kandidata.
S druge strane, često se javljaju i problemi za koje ne postoji unapred poznata matematička formula kojom se izračunava tražena vrednost. U takvim situacijama neophodno je upotrebiti računarsku snagu da bi se do rešenja došlo iterativnim postupcima (sabiranjem puno sabiraka, analizom puno kandidata za rešenje i slično).
Kao što je već rečeno, i neki čuveni algoritmi i njihove optimizacije su zasnovane na jednostavnim tehnikama koje u ovom poglavlju opisujemo. Jedan od njih je i Euklidov algoritam. Originalna varijanta Euklidovog algoritma za pronalaženje NZD dva broja pronalazi NZD tako što od većeg pozitivnog prirodnog broja oduzima manji sve dok manji od njih ne postane nula.
int nzd(int a, int b) {
while (b != 0) {
if (a > b)
a -= b;
else
b -= a;
}
return a;
}Program ispravno radi kada su \(a\) i \(b\) pozitivni, ispravno radi i kada je \(b=0\), ali se ne zaustavlja kada je \(a=0\) (što se lako može ispraviti ispitivanjem tog specijalnog slučaja i vraćanjem vrednosti \(b\) na početku funkcije ili tako što se uslov petlje promeni da se program zaustavlja kada bilo koja promenljiva postane 0, a kao rezultat vrati vrednost one druge promenljive).
U slučaju kada je jedan od ovih brojeva dosta manji od drugog, ovo je veoma sporo. Na primer, za \(a=135\) i \(b=12\) dobija se sledeći niz vrednosti:
| a | 135 | 123 | 111 | 99 | 87 | 75 | 63 | 51 | 39 | 27 | 15 | 3 | 3 | 3 | 3 | 3 |
| b | 12 | 12 | 12 | 12 | 12 | 12 | 12 | 12 | 12 | 12 | 12 | 12 | 9 | 6 | 3 | 0 |
Ceo dugački iterativni niz izračunavanja kojim se vrednost \(135\) smanjuje do \(3\) se može ukloniti kada se primeti da će se broj \(12\) oduzimati od veće vrednosti sve dok se broj \(a\) ne smanji do vrednosti ostatka pri deljenju polaznog broja \(145\) brojem \(12\), a to je \(3\). Zatim će se ta vrednost \(3\) oduzimati iterativno od broja \(12\) sve dok se broj \(b\) ne smanji do vrednosti ostatka pri deljenju broja \(12\) brojem \(3\) a to je \(0\). Dakle, umesto da u svakom koraku iterativno smanjujemo broj oduzimanjem, ovaj dugačak postupak možemo zameniti jednim korakom izračunavanja ostatka pri deljenju. Tako dobijamo sledeći algoritam.
int nzd(int a, int b) {
while (b != 0) {
int ostatak = a % b;
a = b;
b = ostatak;
}
return a;
}Na ovaj način dobijamo sledeću tabelu izvršavanja za brojeve \(a=145\) i \(b=12\).
| a | 135 | 12 | 3 |
| b | 12 | 3 | 0 |
Primetimo da u varijanti sa deljenjem nije potrebno porediti vrednosti \(a\) i \(b\). Ako je vrednost \(a\) manja od \(b\), tada je \(a \,\mathrm{mod}\,b = a\), pa se od para \((a, b)\) dobija par \((b, a\,\mathrm{mod}\,b) = (b, a)\) tj. u prvom koraku se vrednosti razmenjuju. Pošto je \(a\,\mathrm{mod}\,b < b\), nadalje važi da će vrednost \(a\) biti veća od vrednosti \(b\).
Složenost najgoreg slučaja polazne varijante algoritma – varijante sa oduzimanjem je \(O(\max(a, b))\), jer najgori slučaj nastupa kada je vrednost manjeg od dva broja jednaka \(1\). U novom algoritmu – u varijanti sa deljenjem, asimptotska složenost značajno je redukovana. Naime, u svaka dva koraka algoritma vrednost broja \(a\) smanji bar upola. Zaista, u prvom koraku se od para brojeva \((a, b)\) dobija par brojeva \((b, a\,\mathrm{mod}\,b)\), a u drugom se dobija par brojeva \((a\,\mathrm{mod}\,b, b\,\mathrm{mod}\,(a \,\mathrm{mod}\,b))\). Tvrdimo da je \(a \,\mathrm{mod}\,b \leq \frac{a}{2}\). Zaista, ako je \(b \leq \frac{a}{2}\), tada je \(a\,\mathrm{mod}\,b < b \leq \frac{a}{2}\). Ako je \(b > \frac{a}{2}\), tada je \(a \,\mathrm{mod}\,b = a - b < a - \frac{a}{2} = \frac{a}{2}\). Zato je dvostruki broj koraka koji se može sprovesti u najgorem slučaju \(\log_2(\max(a, b))\), pa je složenost ove varijante algoritma jednaka \(O(\log(\max(a, b)))\).
Primetimo da smo složenost iskazali u terminima ulaznih vrednosti \(a\) i \(b\). Ako se složenost iskazuje u terminima veličine zapisa ulaza, onda je potrebno izraziti ju je u terminima broja cifara vrednosti \(a\) i \(b\), a koji logaritamski zavisi od njihovih vrednosti. Dakle, u tom slučaju varijanta sa oduzimanjem ima eksponencijalnu, a varijanta sa deljenjem linearnu složenost u odnosu na veličinu ulaza.
Ilustrujmo tehniku optimizacije zamenom iteracije formulom kroz još nekoliko jednostavnih problema.
Data je binarna niska (niska karaktera koja se sastoji od karaktera 0 i 1). Napisati program kojim se određuje broj segmenata (podniski uzastopnih elemenata) u datoj niski koji su dužine najmanje 2, a koji počinju i završavaju sa 1.
Prva i jedina linija standardnog ulaza sadrži binarnu nisku (sastavljenu od 0 i 1).
Na standardnom izlazu prikazati traženi broj segmenata.
010001001
3
To su podniske 10001, 10001001 i 1001.
Broj svih segmenata koji počinju i završavaju sa 1 možemo jednostavno odrediti analizirajući sve segmente. U spoljašnjoj petlji analiziramo jedan po jedan karakter. Svaku jedinicu na koju naiđemo (za svako \(i\) takvo da je \(s_i\) jednako 1), razmatramo kao početak segmenta i u unutrašnjoj petlji (brojačem \(j\) od \(i+1\) do kraja niske) tražimo jedinicu kojom se segment završava. Za svaku jedinicu pronađenu u unutrašnjoj petlji (za svako \(j\) takvo da je \(s_j\) jednako 1) uvećavamo broj segmenata.
int broj1x1Podniski(const string& s) {
int n = s.length();
int br = 0;
for (int i = 0; i < n - 1; i++)
if (s[i] == '1')
for (int j = i + 1; j < n; j++)
if (s[j] == '1')
br++;
return br;
}#include <iostream>
#include <string>
using namespace std;
int broj1x1Podniski(const string& s) {
int n = s.length();
int br = 0;
for (int i = 0; i < n - 1; i++)
if (s[i] == '1')
for (int j = i + 1; j < n; j++)
if (s[j] == '1')
br++;
return br;
}
int main() {
string s;
cin >> s;
cout << broj1x1Podniski(s) << endl;
return 0;
}Primetimo da na ovaj način iste karaktere niske nepotrebno analiziramo veliki broj puta. Složenost algoritma odgovara ukupnom broju svih segmenata i jednaka je \(O(n^2)\).
Svaki segment koji počinje i koji se zavrašava jedinicom definisan je pozicijama dve jedinice u niski, pa je ukupan broj traženih segmenata jednak broju načina da se izaberu dve različite jedinice u niski. Ako je ukupan broj jedinica u niski jednak \(b\) onda dve jedinice možemo izabrati na \(\frac {b \cdot (b - 1)}{2}\) načina.
int broj1x1Podniski(const string& s) {
int brojJedinica = 0;
for (char c : s)
if (c == '1')
brojJedinica++;
return brojJedinica * (brojJedinica - 1) / 2;
}#include <iostream>
#include <string>
using namespace std;
int broj1x1Podniski(const string& s) {
int brojJedinica = 0;
for (char c : s)
if (c == '1')
brojJedinica++;
return brojJedinica * (brojJedinica - 1) / 2;
}
int main() {
string s;
cin >> s;
cout << broj1x1Podniski(s) << endl;
return 0;
}Pošto jedinice prebrojavamo samo jednim prolaskom kroz nisku, složenost ovog algoritma je \(O(n)\).
Ovaj problem se lako uopštava na, na primer, brojanje svih podniski koje počinju i završavaju se istim karakterom u datom tekstu. Ovakve statistike teksta mogu biti korisne u analizi podataka, bioinformatici (na primer, analizi DNK sekvenci) i slično.
Napisati program koji ispisuje sve trojke prirodnih brojeva \(a, b, c\), takve da je \(a^2 + b^2 = c^2\), a u kojima važi \(a \leq b \leq c \leq n\).
Sa standardnog ulaza se učitava prirodan broj \(n \leq 5 \cdot 10^5\).
Na standardni izlaz ispisati u leksikografskiom redosledu tražene trojke brojeva, svaku u posebnom redu, sa po jednim razmakom između brojeva.
17
3 4 5 5 12 13 6 8 10 8 15 17 9 12 15
Zadatak možemo da rešimo formiranjem svih trojki \((a, b, c)\), u kojima je \(a \leq b \leq c \leq n\) i ispisivanjem onih koje ispunjavaju Pitagorin uslov \(a^2 + b^2 = c^2\).
for (int a = 1; a <= n; a++)
for (int b = a; b <= n; b++)
for (int c = b; c <= n; c++)
if (a*a + b*b == c*c)
cout << a << " " << b << " " << c << " " << endl;#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
for (int a = 1; a <= n; a++)
for (int b = a; b <= n; b++)
for (int c = b; c <= n; c++)
if (a*a + b*b == c*c)
cout << a << " " << b << " " << c << " " << endl;
return 0;
}Broj ispitivanja uslova u trostrukoj petlji je srazmeran sa \(n^3\), pa je složenost ovog rešenja \(O(n^3)\).
Primetimo da, kada su vrednosti kateta \(a, b\) fiksirane, hipotenuzu možemo da izračunamo kao \(\sqrt{a^2+b^2}\). Tako, umesto da za vrednost hipotenuze iterativno isprobavamo sve vrednosti od \(b\) do \(n\), dovoljno je da ispitamo da li je izračunata vrednost celobrojna. Time zadatak rešavamo pomoću dvostruke, umesto trostruke petlje, čime rešenje postaje značajno brže. Složenost ovog rešenja je \(O(n^2)\).
for (int a = 1; a <= n; a++)
for (int b = a; a*a + b*b <= n*n; b++) {
double cr = sqrt(a*a + b*b);
int c = round(cr);
if (c == cr)
cout << a << " " << b << " " << c << " " << endl;
}#include <iostream>
#include <cmath>
using namespace std;
int main() {
int n;
cin >> n;
for (int a = 1; a <= n; a++)
for (int b = a; a*a + b*b <= n*n; b++) {
double cr = sqrt(a*a + b*b);
int c = round(cr);
if (c == cr)
cout << a << " " << b << " " << c << " " << endl;
}
return 0;
}Ubrzanje smo ponovo dobili tako što smo izbegli iteraciju na osnovu primene matematičke formule tj. tako što smo izračunali jedinstvenu vrednost koja ima šanse da zadovolji traženi uslov. Česta greška programera je da previde da u nekom skupu postoji jedinstven kandidat za rešenje zadatka i da se taj kandidat može eksplicitno izračunati, umesto da se iterativno pretražuje.