Jedna od osnovnih tehnika za izbegavanje loše složenosti algoritama je da se izbegne izračunavanje istih ili povezanih stvari više puta u istom programu. U računarstvu često imamo potrebu za izračunavanjem određene funkcije nekog skupa podataka (reći ćemo da izračunavamo neku statistiku tih podataka). Kada se podaci promene, menja se i vrednost statistike. Čest je slučaj da se nakon male promene podataka (na primer, proširenja skupa novim podatkom) statistika ne mora računati iz početka, već se može efikasnije izračunati na osnovu poznate vrednosti statistike originalnih podataka i promene koje su se desile nad podacima. Ovo je ilustrovano na slici 13.
Veoma jednostavan primer principa inkrementalnosti je izračunavanje zbirova prefiksa (tzv. parcijalnih zbirova) elemenata nekog niza. Na primer, ako je dat niz \(1, 2, 3, 4, 5\), njegovi parcijalni zbirovi su redom \(0, 1, 3, 6, 10, 15\) (o značaju prefiksnih zbirova biće više reči u poglavlju 3.4). Veoma jednostavno se primećuje da se izračunavanje narednog parcijalnog zbira ne mora vršiti sabiranjem svih elemenata od početka, već se može dobiti sabiranjem prethodnog parcijalnog zbira sa tekućim elementom niza (na primer, zbir \(1+2+3+4 = 10\), se dobija sabiranjem prethodnog zbira \(1+2+3 = 6\) i tekućeg elementa \(4\)). Ako zbir prvih \(k\) elemenata niza označimo sa \(Z_k\), tada važi:
\[Z_0 = 0, \quad Z_{k+1} = Z_k + a_k, k > 0.\]
Ovim smo dobili seriju brojeva u kojoj se naredni element izračunava na osnovu prethodnog (ili nekoliko prethodnih). Za takve serije kažemo da su rekurentne serije. Svaki naredni član se izračunava u složenosti \(O(1)\), pa se izračunavanje svih parcijalnih zbirova niza dužine \(n\) vrši u složenosti \(O(n)\). Kada bi se svaki parcijalni zbir računao sabiranjem elemenata niza iz početka, tada bi izračunavanje \(k\)-tog zbira bilo složenosti \(O(k)\), a izračunavanje svih zbirova složenosti \(O(n^2)\).
Princip inkrementalnosti je u tesnoj vezi sa induktivno/rekurzivnom konstrukcijom algoritama i leži u osnovi velikog broja osnovnih algoritama. Izračunavanje zbira svih elemenata niza zapravo počiva na postepenom, inkrementalnom izračunavanju zbirova prefiksa, sve dok se ne izračuna zbir svih elemenata niza. Slično je i sa izračunavanjem minumuma, maksimuma, linearnom pretragom i drugim fundamentalnim algoritmima. U svim ovim primerima krećemo od neke početne vrednosti u nizu rezultata, a zatim narednu vrednost u tom nizu izračunavamo na osnovu prethodne ili nekoliko prethodnih, što direktno odgovara induktivnom postupku izračunavanja. Slična tehnika (dobijanja narednih rezultata na osnovu prethodnih) primenjuje se u sklopu tehnike dinamičkog programiranja naviše, o čemu će više reči biti u poglavlju @sec:dp.
Pored parcijalnih zbirova, inkrementalno se mogu izračunavati i parcijalni proizvodi, parcijalni minimumi i maksimumi i slično, ali i mnoge druge, naprednije statistike. Ilustrujmo ovu tehniku kroz nekoliko primera.
Želimo da obezbedimo anonimnost sistema za elektronsko glasanje tako što će se nakon glasanja izvršiti permutovanje glasova i to tako da nijedan glas ne ostane uz osobu koja ga je dala. Permutacija je deranžman (engl. derangement) ako se nijedan element ne nalazi na svojoj originalnoj poziciji (na primer, permutacija \(4321\) jeste deranžman za elemente \(1234\), dok permutacija \(3241\) nije deranžman, jer se element \(2\) nalazi na poziciji \(2\)). Verovatnoća da je nasumično izabrana permutacija dužine \(n\) deranžman (tj. da anonimnost glasanja \(n\) glasača bude obezbeđena nasumično odabranom permutacijom) može se izračunati na osnovu formule \(\sum_{k=0}^{n}\frac{(-1)^k}{k!} = 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} \ldots + \frac{(-1)^n}{n!}.\) Napisati program koji izračunava ovu verovatnoću.
Napomena: Pošto važi
\[e^x = \sum_{k=0}^{+\infty} \frac{x^k}{k!},\]
sa povećanjem broja \(n\) ova verovatnoća teži vrednosti \(e^{-1} = 1/e \approx 36,\!79\%\ldots\).
Sa standardnog ulaza se učitava broj \(n\) (\(2 \leq n \leq 20\)).
Na standardni izlaz ispisati traženu verovatnoću, zaokruženu na 14 decimala.
2
0.500000000000000
10
0.367879464285714
Direktan način da se izračuna tražena verovatnoća je da se izračuna zbir serije brojeva koja se dobija tako što se za svako \(k\) od 0 do \(n\) izračuna vrednost \(\frac{(-1)^k}{k!}\). Stepen \((-1)^k\) se može izračunati funkcijom pow ili se može odrediti grananjem, pošto je \((-1)^k = 1\) za parne vrednosti \(k\) i \((-1)^k = -1\) za neparne vrednosti \(k\). Faktorijel \(k!\) se može izračunati množenjem serije brojeva od \(1\) do \(k\).
// faktorijel broja n
double faktorijel(int n) {
double p = 1.0;
for (int i = 2; i <= n; i++)
p *= i;
return p;
}
// zbir 1 - 1/1! + 1/2! + ... + (-1)^n/n!
double verovatnoca(int n) {
double p = 0.0;
for (int k = 0; k <= n; k++)
p += pow(-1, k) / faktorijel(k);
return p;
}#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
// faktorijel broja n
double faktorijel(int n) {
double p = 1.0;
for (int i = 2; i <= n; i++)
p *= i;
return p;
}
// zbir 1 - 1/1! + 1/2! + ... + (-1)^n/n!
double verovatnoca(int n) {
double p = 0.0;
for (int k = 0; k <= n; k++)
p += pow(-1, k) / faktorijel(k);
return p;
}
int main() {
int n;
cin >> n;
cout << fixed << showpoint << setprecision(14)
<< verovatnoca(n) << endl;
return 0;
}Izračunavanje \(k\)-tog sabirka zahteva \(O(k)\) operacija, pa je za sabiranje \(n\) sabiraka potrebno vreme \(O(n^2)\).
Problem sa ovim pristupom nije samo vremenska složenost. Pošto faktorijeli veoma brzo rastu, postoji opasnost da za veće vrednosti \(k\) nastupi prekoračenje prilikom izračunavanja \(k!\) (čak i kada se koristi tip podataka double). Slično, ako se računa \(\frac{x^k}{k!}\), za \(x > 1\), tada i brojilac raste veoma brzo, pa i tu preti opasnost od prekoračenja, iako je vrednost razlomka sve bliža i bliža nuli.
Efikasnije rešenje se može dobiti ako se uoči da brojevi \(1 = \frac{(-1)^0}{0!}\), \(-1 = \frac{(-1)^1}{1!}\), \(\frac{1}{2} = \frac{(-1)^2}{2!}\), \(-\frac{1}{6} = \frac{(-1)^3}{3!}\) itd. čine veoma pravilnu seriju u kojoj se svaki naredni član može dobiti množenjem prethodnog člana vrednošću \(-\frac{1}{k}\). Dakle, u ovom zadatku se koristi kako inkrementalnost serije parcijalnih zbirova (u sklopu algoritma sabiranja), tako i inkrementalnost serije samih sabiraka, koji su zapravo parcijalni proizvodi pravilne serije \(-\frac{1}{1}, -\frac{1}{2}, -\frac{1}{3}, -\frac{1}{4}, \ldots\) Ako sa \(x_k\) obeležimo sabirak \(k\), tada je \(x_0 = \frac{(-1)^0}{0!} = 1\), dok je \(x_{k+1} = -\frac{1}{k} \cdot x_k\).
Tokom implementacije ćemo održavati dve promenljive. Prva će da predstavlja zbir do sada sabranih sabiraka, a druga tekući sabirak. Zbir i tekući član inicijalizovaćemo na vrednost 1 (to je vrednost \(\frac{(-1)^0}{0!}\)). U svakom koraku petlje u kojoj \(k\) uzima vrednosti od 1 do \(n\) tekući član ćemo ažurirati množenjem sa vrednošću \(-\frac{1}{k}\) i dodavaćemo ga na zbir. Nakon završetka petlje, zbir će sadržati traženu verovatnoću koju ćemo ispisati sa traženim brojem decimala.
Dobar savet prilikom izračunavanja zbirova ovog tipa je da se izračuna količnik dva susedna sabirka i da se proveri da li se on možda veoma jednostavno izračunava u funkciji od \(k\) (u ovom slučaju taj količnik je \(\frac{-1}{k}\)). Umesto količnika, u nekim zadacima je pogodnije razmatrati razliku dva uzastopna sabirka.
// verovatnoca je jednaka zbiru
// 1 - 1/1! + 1/2! + ... + (-1)^n/n!
double verovatnoca(int n) {
double p = 1.0;
// tekuci element zbira (-1)^k/k!
double xk = 1.0;
for (int k = 1; k <= n; k++) {
// izracunavamo sledeci clan mnozenjem prethodnog sa -1/k
xk *= -1.0/k;
// dodajemo ga na z
p += xk;
}
return p;
}#include <iostream>
#include <iomanip>
using namespace std;
// verovatnoca je jednaka zbiru
// 1 - 1/1! + 1/2! + ... + (-1)^n/n!
double verovatnoca(int n) {
double p = 1.0;
// tekuci element zbira (-1)^k/k!
double xk = 1.0;
for (int k = 1; k <= n; k++) {
// izracunavamo sledeci clan mnozenjem prethodnog sa -1/k
xk *= -1.0/k;
// dodajemo ga na z
p += xk;
}
return p;
}
int main() {
int n;
cin >> n;
cout << fixed << showpoint << setprecision(14)
<< verovatnoca(n) << endl;
return 0;
}Izračunavanje \(k\)-tog sabirka na osnovu prethodnog zahteva samo \(O(1)\) operacija, pa se izračunavanje zbira \(n\) sabiraka vrši u vremenu \(O(n)\). Doduše, u ovom zadatku \(n\) je veoma mali broj, pa se na ovaj način ne postiže značajno ubrzanje, ali u drugim sličnim zadacima optimizacija na osnovu inrementalnosti može biti veoma značajna.
Duž jedne ulice su ravnomerno raspoređene zgrade (rastojanje između svake dve susedne je jednako). Za svaku zgradu je poznat broj stanova koje novi dobavljač interneta treba da poveže. Svaki stan se povezuje posebnim optičkim kablom sa ruterom. Odrediti u koju od zgrada treba postaviti ruter tako da ukupna dužina optičkih kablova kojim se svaki od stanova povezuje sa ruterom bude minimalna (računati samo dužinu kablova od zgrade do zgrade i zanemariti dužine unutar zgrada).
U prvom redu standardnog ulaza nalazi se broj \(n\) (\(1 \leq n \leq 10^5\)), a u narednom \(n\) prirodnih brojeva razdvojenih razmacima koji predstavljaju broj stanova u svakoj od \(n\) zgrada.
Na standardni izlaz ispisati minimalnu dužinu kablova.
6 3 5 1 6 2 4
30
Ruter treba postaviti u četvrtu zgradu sleva i dužina kablova je tada jednaka \(3\cdot 3 + 2\cdot 5 + 1\cdot 1 + 1\cdot 2 + 2 \cdot 4 = 30\).
Direktno rešenje bi podrazumevalo da se izračuna dužina kablova za svaku moguću poziciju rutera i da se odabere najmanji. Da bismo izračunali dužinu kablova, ako je ruter u zgradi na poziciji \(k\), računamo zapravo zbir
\[\sum_{i=0}^{n-1} |k-i|\cdot a_i,\]
gde je \(a_i\) broj stanova u zgradi \(i\).
long long minDuzinaKablova(const vector<int>& broj_stanara) {
// broj zgrada
int n = broj_stanara.size();
// minimalna duzina kablova
long long min_duzina_kablova =
numeric_limits<long long>::max();
// obrađujemo sve zgrade od 1 do n-1
for (int k = 0; k < n; k++) {
// duzina kablova ako je ruter u zgradi broj k
long long duzina_kablova = 0;
for (int i = 0; i < k; i++)
duzina_kablova += (k - i) * broj_stanara[i];
for (int i = k+1; i < n; i++)
duzina_kablova += (i - k) * broj_stanara[i];
if (duzina_kablova < min_duzina_kablova)
min_duzina_kablova = duzina_kablova;
}
return min_duzina_kablova;
}#include <iostream>
#include <vector>
#include <limits>
using namespace std;
long long minDuzinaKablova(const vector<int>& broj_stanara) {
// broj zgrada
int n = broj_stanara.size();
// minimalna duzina kablova
long long min_duzina_kablova =
numeric_limits<long long>::max();
// obrađujemo sve zgrade od 1 do n-1
for (int k = 0; k < n; k++) {
// duzina kablova ako je ruter u zgradi broj k
long long duzina_kablova = 0;
for (int i = 0; i < k; i++)
duzina_kablova += (k - i) * broj_stanara[i];
for (int i = k+1; i < n; i++)
duzina_kablova += (i - k) * broj_stanara[i];
if (duzina_kablova < min_duzina_kablova)
min_duzina_kablova = duzina_kablova;
}
return min_duzina_kablova;
}
int main() {
int n;
cin >> n;
vector<int> broj_stanara(n);
for (int i = 0; i < n; i++)
cin >> broj_stanara[i];
cout << minDuzinaKablova(broj_stanara) << endl;
return 0;
}Svaki težinski zbir možemo izračunati u vremenu \(O(n)\), pa pošto se ispituje \(n\) pozicija, algoritam je složenosti \(O(n^2)\).
Mnogo bolje rešenje i algoritam linearne složenosti možemo dobiti ako primenimo princip inkrementalnosti i izbegnemo računanje u svakom koraku iz početka. Razmotrimo kako se dužina kablova menja kada se ruter pomera sa zgrade \(k\) na zgradu \(k+1\).
Dužinu kablova za ruter u zgradi \(k+1\) dobijamo od dužine kablova za ruter u zgradi \(k\) tako što tu dužinu uvećamo za ukupan broj stanova zaključno sa zgradom \(k\) i umanjimo je za ukupan broj stanova počevši od zgrade \(k+1\). To je intuitivno jasno i bez strogog matematičkog izvođenja. Pomeranjem rutera u narednu zgradu, svakom stanu zaključno do zgrade \(k\) dužina kabla se povećala za jedno rastojanje između zgrada, a svim stanovima od zgrade \(k+1\) nadesno se ta dužina smanjuje za jedno rastojanje između zgrada.
Formalno, matematički, to se može pokazati na sledeći način. Ako je ruter na poziciji \(k\), tada je dužina kablova jednaka
\[d_k = \sum_{i=0}^{k-1} (k-i)\cdot a_i + \sum_{i=k+1}^{n-1} (i-k)\cdot a_i.\]
Ako je ruter na poziciji \(k+1\), tada je dužina kablova jednaka
\[d_{k+1} = \sum_{i=0}^{k} (k+1-i)\cdot a_i + \sum_{i=k+2}^{n-1} (i-k-1)\cdot a_i.\]
Razlika između te dve sume jednaka je
\[\begin{eqnarray*} d_{k+1} - d_k &=& \left(\sum_{i=0}^{k} (k+1-i) \cdot a_i - \sum_{i=0}^{k-1} (k-i)\cdot a_i\right) + \\ & & \left(\sum_{i=k+2}^{n-1} (i-k-1)\cdot a_i - \sum_{i=k+1}^{n-1} (i - k) \cdot a_i\right)\\ &=& \left(\sum_{i=0}^{k-1} ((k+1-i) - (k-i)) \cdot a_i\right) + a_k \\ & & - a_{k+1} + \left(\sum_{i=k+2}^{n-1}((i-k-1) - (i-k)) \cdot a_i\right)\\ &=& \sum_{i=0}^{k-1}a_i + a_k - a_{k-1} - \sum_{i=k+2}^{n-1} a_i\\ &=& \sum_{i=0}^ka_i - \sum_{i=k+1}^{n-1}a_i \end{eqnarray*}\]
Ukupne brojeve stanova pre i posle date zgrade možemo takođe računati inkrementalno (pri prelasku na narednu zgradu, prvi broj se uvećava, a drugi umanjuje za broj stanova u tekućoj zgradi).
Dakle, u programu možemo da pamtimo tri stvari: dužinu kablova \(d_k\) ako je ruter na poziciji \(k\), ukupan broj stanova \(pre_k\) pre zgrade \(k\) (ne uključujući nju) i ukupan broj stanova \(posle_k\) od zgrade \(k\) (uključujući nju) do kraja. Na početku, kada je \(k=0\), prvi broj \(d_0\) moramo eksplicitno izračunati kao \(\sum_{i=1}^{n-1}i \cdot a_i\), drugi broj treba inicijalizovati na nulu \(pre_0 = 0\), a treći na ukupan broj svih stanova \(posle_k = \sum_{i=0}^{n-1}a_i\). Zatim za svako \(k\) od \(1\) do \(n-1\) računamo \(pre_k = pre_{k-1} + a_{k-1}\), \(posle_k = posle_{k-1} - a_{k-1}\) i zatim \(d_k = d_{k-1} + pre_k - posle_k\).
Primer 3.2.1. Ilustrujmo izvršavanje ovog algoritma na primeru zgrada u kojima živi redom \(3, 5, 1, 6, 2, 4\) stanara.
| \(k\) | \(d_k\) | \(\mathit{pre}_k\) | \(\mathit{posle}_k\) |
|---|---|---|---|
| 0 | 53 | 0 | 21 |
| 1 | 38 | 3 | 18 |
| 2 | 33 | 8 | 13 |
| 3 | 30 | 9 | 12 |
| 4 | 39 | 15 | 6 |
| 5 | 52 | 17 | 4 |
long long minDuzinaKablova(const vector<int>& broj_stanova) {
// broj zgrada
int n = broj_stanova.size();
// krećemo od zgrade 0
// ukupna dužina kablova ako je ruter u tekućoj zgradi
long long duzina_kablova = 0;
for (int i = 0; i < n; i++)
duzina_kablova += broj_stanova[i] * i;
// broj stanova pre tekuće zgrade
long long stanova_pre = 0;
// broj stanova od tekuće zgrade do kraja
long long stanova_posle = 0;
for (int i = 0; i < n; i++)
stanova_posle += broj_stanova[i];
// minimalna duzina kablova
long long min_duzina_kablova = duzina_kablova;
// obrađujemo sve zgrade od 1 do n-1
for (int k = 1; k < n; k++) {
// ažuriramo brojeve stanova
stanova_pre += broj_stanova[k-1];
stanova_posle -= broj_stanova[k-1];
// ažuriramo duzinu kablova
duzina_kablova += stanova_pre - stanova_posle;
// ažuriramo minimum ako je potrebno
if (duzina_kablova < min_duzina_kablova)
min_duzina_kablova = duzina_kablova;
}
return min_duzina_kablova;
}#include <iostream>
#include <vector>
using namespace std;
long long minDuzinaKablova(const vector<int>& broj_stanova) {
// broj zgrada
int n = broj_stanova.size();
// krećemo od zgrade 0
// ukupna dužina kablova ako je ruter u tekućoj zgradi
long long duzina_kablova = 0;
for (int i = 0; i < n; i++)
duzina_kablova += broj_stanova[i] * i;
// broj stanova pre tekuće zgrade
long long stanova_pre = 0;
// broj stanova od tekuće zgrade do kraja
long long stanova_posle = 0;
for (int i = 0; i < n; i++)
stanova_posle += broj_stanova[i];
// minimalna duzina kablova
long long min_duzina_kablova = duzina_kablova;
// obrađujemo sve zgrade od 1 do n-1
for (int k = 1; k < n; k++) {
// ažuriramo brojeve stanova
stanova_pre += broj_stanova[k-1];
stanova_posle -= broj_stanova[k-1];
// ažuriramo duzinu kablova
duzina_kablova += stanova_pre - stanova_posle;
// ažuriramo minimum ako je potrebno
if (duzina_kablova < min_duzina_kablova)
min_duzina_kablova = duzina_kablova;
}
return min_duzina_kablova;
}
int main() {
int n;
cin >> n;
vector<int> broj_stanova(n);
for (int i = 0; i < n; i++)
cin >> broj_stanova[i];
cout << minDuzinaKablova(broj_stanova) << endl;
return 0;
}Primetimo da je moguće izvršiti i malu optimizaciju (doduše koja neće popraviti asimptotsku složenost) na osnovu monotonosti niza \(d_k\) i petlju prekinuti čim se broj \(d_k\) prvi put poveća.
Pošto je i za jednu i za drugu fazu potrebno vreme \(O(n)\), to je ujedno složenost ovog algoritma.