Jedan od osnovnih principa za dobijanje efikasnijih algoritama i programa je da računar ne treba da izračunava stvari za koje se unapred može proceniti da nisu potrebne za dobijanje konačnog rešenja problema. Važan primer ovog principa se javlja kod algoritama pretrage. Pretragu elemenata ne treba eksplicitno vršiti među elementima za koje se može unapred utvrditi da ne mogu da zadovolje uslov pretrage. Kada preskočimo proveru takvih elemenata, kažemo da smo učinili odsecanje u pretrazi. Sličan princip se primenjuje i kada se vrši optimizacija tj. traži najveći (odnosno najmanji) element. Tada se može preskočiti eksplicitna provera elemenata za koje se unapred može dokazati da su manji (odnosno veći) od traženog maksimuma (odnosno minimuma).
Da bi se osigurala korektnost algoritama u kojima se vrši odsecanje, potrebno je nesumnjivo utvrditi da je odsecanje opravdano i da se u delu prostora pretrage koji se ne ispituje zaista ne može nalaziti rešenje problema.
U nastavku ovog poglavlja ćemo kroz određen broj primera prikazati kako se odsecanjem postiže asimptotski efikasniji algoritam. Jedan od najznačajnijih primera odsecanja predstavlja binarna pretraga, koja će, zbog svog značaja biti analizirana u posebnom poglavlju 3.6. Odsecanje se primenjuje i u drugim oblicima pretrage (bektreking pretrazi, pretrazi u dubinu, pretrazi u širinu), o čemu će više biti reči u kasnijim poglavljima.
Napiši program koji ispituje da li je uneti prirodan broj prost (veći je od 1 i nema drugih delilaca osim 1 i samog sebe).
Sa standardnog ulaza se unosi prirodan broj \(n\) (\(1 \leq n \leq 10^9\)).
Na standardni izlaz ispisati DA ako je broj \(n\) prost tj. NE ako nije.
17
DA
903543481
NE
Prirodan broj je prost ako je veći od 1 i ako nije deljiv ni sa jednim brojem osim sa 1 i sa samim sobom. Po definiciji broj 1 nije prost. Dakle, broj veći od 1 je prost ako nema ni jednog pravog delioca. Potrebno je dakle proveriti da li neki element skupa potencijalnih delilaca stvarno deli broj \(n\) (brojeva od \(2\) do \(n-1\)). Implementacija se zasniva na algoritmu linearne pretrage. Naivna implementacija proverava sve elemente skupa brojeva od \(2\) do \(n-1\).
// funkcija koja proverava da li je dati broj prost
bool prost(int n) {
if (n == 1) return false;
for (int i = 2; i < n; i++)
if (n % i == 0)
return false;
return true;
}#include <iostream>
using namespace std;
// funkcija koja proverava da li je dati broj prost
bool prost(int n) {
if (n == 1) return false;
for (int i = 2; i < n; i++)
if (n % i == 0)
return false;
return true;
}
int main() {
int n;
cin >> n;
cout << (prost(n) ? "DA" : "NE") << endl;
return 0;
}Pošto se provera svakog delioca izvršava izračunavanjem jednog ostatka pri deljenju, u složenosti \(O(1)\), složenost ovog pristupa odgovara broju delilaca i jednaka je \(O(n)\).
Delioci broja se uvek javljaju u paru. Na primer, delioci broja 100 organizovani po parovima su (1, 100), (2, 50), (4, 25) (5, 20) i (10, 10). Ako je \(i\) delilac broja \(n\), delilac je i broj \(\frac{n}{i}\). Pri tom, ako je \(i \geq \sqrt{n}\), tada je \(\frac{n}{i} \leq \sqrt{n}\). Dakle, važi sledeća teorema.
Teorema. Prirodan broj \(n \geq 2\) ima prave delioce koji su veći ili jednaki vrednosti \(\sqrt{n}\) ako i samo ako ima delioce koji su manji ili jednaki vrednosti \(\sqrt{n}\).
Ova teorema nam daje mogućnost da pretragu potencijalnih delilaca redukujemo samo na interval \([2, \sqrt{n}]\), jer ako broj nema delilaca manjih ili jednakih vrednosti \(\sqrt{n}\), onda ne može da ima delilaca većih ili jednakih toj vrednosti, tj. nema pravih delilaca i prost je. Ovo je primer algoritma u kom se efikasnost značajno popravlja tako što je eliminisan (odsečen) značajan deo prostora pretrage za koji smo uspeli da dokažemo da ga nije neophodno proveravati.
Sama implementacija je jednostavna i zasniva se ponovo na algoritmu linearne pretrage. U posebnoj funkciji na početku proveravamo specijalan slučaj broja 1. Nakon toga, u petlji proveravamo potencijalne delioce od 2 do \(\sqrt{n}\). Jedan način da odredimo gornju granicu je da upotrebimo bibliotečku funkciju sqrt. Međutim, rad sa realnim brojevima je moguće u potpunosti izbeći tako što se umesto uslova \(i \leq \sqrt{n}\) upotrebi uslov \(i\cdot i \leq n\). Za svaku vrednost \(i\) proverava se da li je delilac broja \(i\) (izračunavanjem ostatka pri deljenju). Čim se utvrdi da je \(i\) delilac broja \(n\) funkcija može da vrati false (time se ujedno prekida izvršavanje petlje). Na kraju petlje, funkcija može da vrati true, jer nije pronađen nijedan delilac manji ili jednak od \(\sqrt{n}\), pa na osnovu teoreme koje smo dokazali ne može postojati ni jedan delilac iznad te vrednosti i broj je prost.
// funkcija koja proverava da li je dati broj prost
bool prost(int n) {
if (n == 1) return false;
for (int i = 2; i*i <= n; i++)
if (n % i == 0)
return false;
return true;
}#include <iostream>
using namespace std;
// funkcija koja proverava da li je dati broj prost
bool prost(int n) {
if (n == 1) return false;
for (int i = 2; i*i <= n; i++)
if (n % i == 0)
return false;
return true;
}
int main() {
int n;
cin >> n;
cout << (prost(n) ? "DA" : "NE") << endl;
return 0;
}Složenost ovog algoritma je \(O(\sqrt{n})\). Ovo skraćivanje intervala pretrage veoma je značajno (ako je najveći broj oko \(10^9\) tj. oko milijardu, umesto milijardu delilaca potrebno je proveravati samo njih koren iz milijardu, što je tek nešto iznad trideset hiljada).
Naravno, isti algoritam se može implementirati i na drugačije načine.
Još jedna moguća optimizacija zasnovana na dodatnom odsecanju je da se na početku proveri da li je broj paran a da se nakon toga proveravaju samo neparni delioci (jer neparan broj ne može imati parne delioce).
// funkcija koja proverava da li je dati broj prost
bool prost(int n) {
if (n == 1) return false; // broj 1 nije prost
if (n == 2) return true; // broj 2 jeste prost
if (n % 2 == 0) return false; // ostali parni nisu prosti
// proveravamo neparne delioce od 3 do korena iz n
for (int i = 3; i*i <= n; i += 2)
if (n % i == 0)
return false;
// nismo nasli delioca - broj jeste prost
return true;
}#include <iostream>
using namespace std;
// funkcija koja proverava da li je dati broj prost
bool prost(int n) {
if (n == 1) return false; // broj 1 nije prost
if (n == 2) return true; // broj 2 jeste prost
if (n % 2 == 0) return false; // ostali parni nisu prosti
// proveravamo neparne delioce od 3 do korena iz n
for (int i = 3; i*i <= n; i += 2)
if (n % i == 0)
return false;
// nismo nasli delioca - broj jeste prost
return true;
}
int main() {
int n;
cin >> n;
cout << (prost(n) ? "DA" : "NE") << endl;
return 0;
}Složenost ovog algoritma je \(O(\sqrt{n})\), ali se proverom samo neparnih brojeva konstantni faktor smanjio dva puta. Dakle, ova optimizacija ne donosi previše. Kada je \(n\) prost broj oko milijardu, obilazak do korena smanjuje broj potencijalih kandidata sa milijarde na tek tridesetak hiljada, a provera samo neparnih delilaca taj broj smanjuje na petnaestak hiljada, što je znatno manja ušteda.
Program se još malo može ubrzati ako se primeti da su svi prosti brojevi veći od 2 i 3 oblika \(6k-1\) ili \(6k+1\), za \(k \geq 1\) (naravno, obratno ne važi). Zaista, brojevi oblika \(6k\), \(6k+2\) i \(6k+4\) su sigurno parni tj. deljivi sa \(2\), brojevi oblika \(6k+3\) su deljivi sa \(3\), tako da su jedini preostali \(6k+1\) i \(6k+5\), pri čemu su ovi drugi sigurno oblika \(6k'-1\) (za \(k' = k+1\)). Dakle, umesto da proveravamo deljivost sa svim neparnim brojevima manjim od korena, možemo proveravati deljivost sa svim brojevima oblika \(6k-1\) ili \(6k+1\), čime izbegavamo proveru sa jednim na svaka tri neparna broja i program ubrzamo shodno tome.
Primetimo da se petlja zaustavlja kada je \(6k-1 > \sqrt{n}\) (tada sigurno važi i \(6k+1 > \sqrt{n}\)).
Složenost ovog algoritma je \(O(\sqrt{n})\), ali se proverom samo brojeva oblika 6k-1 i 6k+1 konstantni faktor smanjio tri puta u odnosu na prvi algoritam ove složenosti.
Moguće su još neke optimizacije konstantnih faktora u prethodnim kodovima. Na primer, umesto da se u uslovu petlje množenjem izračunava kvadrat broja, on se može izračunati inkrementalno, uvećavajući kvadrat prethodnog broja. Naime, važi da je \((i+1)^2 = i^2 + 2i + 1\), pa se \((i+1)^2\) može dobiti uvećavanjem \(i^2\) za \(2i+1\), a ta vrednost se može izračunati bez množenja (pomeranjem bitova i sabiranjem). Međutim, ubedljivo najznačajnije ubrzanje je ono asimptotsko, nastalo odsecanjem u pretrazi i njime je program za brojeve reda veličine \(10^9\) ubrzan nekoliko desetina hiljada puta, dok su sve naredne opisane optimizacije ubrzavaju program te po nekoliko puta.
Ako je potrebno za više brojeva odjednom proveriti da li su prosti, umesto proveravanja svakog pojedinačnog, bolje je upotrebiti Eratostenovo sito.
Napisati program koji određuje broj prostih brojeva u intervalu \([a, b]\) i njihov zbir (ako zbir ima više od 6 cifara, ispisati samo ostatak pri deljenju sa \(1\,000\,000\)).
Sa standardnog ulaza unose se brojevi \(a\) i \(b\) (\(1 \leq a \leq b \leq 10^7\)).
Na standardnom izlazu prikazati broj prostih brojeva iz intervala \([a, b]\) i traženi zbir.
1 1000
168 76127
Očigledan algoritam za određivanje svih prostih brojeva iz nekog intervala jeste da se za svaki broj iz tog intervala pojedinačno proveri da li je prost.
Na osnovu specifikacije zadatka potrebno je odrediti najviše 6 poslednjih cifara zbira svih prostih brojeva iz intervala \([a, b]\), što, je ekvivalentno određivanju zbira tih brojeva po modulu \(10^6\). Naime, važi \((a + b) \,\mathrm{mod}\,m = (a \,\mathrm{mod}\,m + b \,\mathrm{mod}\,m) \,\mathrm{mod}\,m\). U petlji prolazimo kroz sve brojeve od \(a\) do \(b\), vršimo filtriranje na osnovu uslova da je broj prost i vršimo brojanje i sabiranje dobijene filtrirane serije.
Napomenimo da se zbir računa tako što se na početku inicijalizuje na nulu, a zatim se u svakom koraku izračunava sabiranje zbira i tekućeg prostog broja po modulu \(10^6\). Pošto će u svakom koraku zbir biti manji od \(10^6\), i pošto ne postoji opasnost od prekoračenja kada se u obzir uzme maksimalna vrednost prostih brojeva koji se sabiraju (pretpostavljajući da tip int može da predstavi brojeve bar do \(10^9\)), sabiranje možemo vršiti naredbom zbir = (zbir + p) % 1000000.
Ako se provera da li je dati broj \(k\) prost vrši u složenosti \(O(\sqrt{k})\), tada je ovaj algoritam složenosti \(O((b-a) \sqrt{b})\). Ako je interval oblika \([0, n]\), složenost je \(O(n\sqrt{n})\).
Bolji rezultat od ispitivanja za svaki broj pojedinačno da li je prost može se dobiti primenom algoritma poznatog kao Eratostenovo sito. Osnovna ideja algoritma je da se prvo napišu svi brojevi od 1 do datog broja \(n\), zatim da se precrta broj 1 (jer on po definiciji nije prost), nakon njega svi umnošci broja 2 osim broja 2 (oni nisu prosti zato što su deljivi sa 2, dok broj 2 ostaje neprecrtan jer je on prost), zatim svi umnošci broja 3 osim broja 3 (oni nisu prosti jer su deljivi brojem 3), zatim umnošci broja 5 osim broja 5 (oni nisu prosti zato što su deljivi brojem 5) i tako dalje.
Efikasna implementacija ovog algoritma podrazumeva nekoliko odsecanja (kojima se izbegava ponavljanje istih operacija više puta i asimptotski ubrzava algoritam).
Prvo i najvažnije, umnoške složenih brojeva nema potrebe posebno precrtavati jer su oni već precrtani tokom precrtavanja umnožaka nekog od njihovih prostih faktora (na primer, nema potrebe posebno precrtavati umnoške broja 4 jer su oni već precrtani tokom precrtavanja umnožaka broja 2). Dakle, kada naiđemo na precrtan broj, njegove umnoške ne precrtavamo.
Drugo, prilikom precrtavanja umnožaka broja \(d\) dovoljno je krenuti od \(d\cdot d\) jer su manji umnošci već precrtani ranije (svi imaju prave faktore manje od \(d\)). Zato je potrebno je da se postupak ponavlja samo dok se ne precrtaju umnošci svih onih prostih brojeva koji nisu veći od korena broja \(n\). Za brojeve veće od korena od \(n\) precrtavanje bi krenulo od njihovog kvadrata koji je veći od \(n\), pa je jasno da se ni za jedan od njih ništa dodatno ne bi precrtalo.
Brojevi koji su ostali neprecrtani su prosti (jer znamo da nemaju pravih delilaca manjih ili jednakih korenu od \(n\), pa samim tim i manjih ili jednakih svom korenu, a pošto nemaju delilaca ispod vrednosti korena, nemaju pravih delilaca ni iznad vrednosti korena).
Primer 3.3.1. Prikažimo kako se ovim algoritmom određuju svi prosti brojevi od 2 do 50. Krećemo od pune tabele u kojoj su upisani svi brojevi od 2 do 50.
. 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
U prvom koraku precrtavamo sve umnoške broja 2 (osim samog broja 2).
. 2 3 . 5 . 7 . 9 . 11 . 13 . 15 . 17 . 19 . 21 . 23 . 25 . 27 . 29 . 31 . 33 . 35 . 37 . 39 . 41 . 43 . 45 . 47 . 49 .
U narednom koraku precrtavamo sve umnoške broja \(3\), krenuvši od njegovog kvadrata tj. od \(9\) (broj \(6\) je već precrtan kao umnožak broja \(2\)).
. 2 3 . 5 . 7 . . . 11 . 13 . . . 17 . 19 . . . 23 . 25 . . . 29 . 31 . . . 35 . 37 . . . 41 . 43 . . . 47 . 49 .
Umnoške broja \(4\) ne precrtavamo, jer je on precrtan (pa samim tim i svi njegovi umnošci).
U narednom koraku precrtavamo sve umnoške broja \(5\), krenuvši od njegovog kvadrata tj. broja \(25\) (umnošci \(2\cdot 5\), \(3\cdot 5\) i \(4\cdot 5\) su već precrtani).
. 2 3 . 5 . 7 . . . 11 . 13 . . . 17 . 19 . . . 23 . . . . . 29 . 31 . . . . . 37 . . . 41 . 43 . . . 47 . 49 .
Umnoške broja \(6\) ne precrtavamo, jer je on precrtan (pa samim tim i svi njegovi umnošci).
Precrtavamo umnoške broja \(7\), krenuvši od njegovog kvadrata tj. broja \(49\).
. 2 3 . 5 . 7 . . . 11 . 13 . . . 17 . 19 . . . 23 . . . . . 29 . 31 . . . . . 37 . . . 41 . 43 . . . 47 . . .
Precrtavanje svih narednih neprecrtanih brojeva bi krenulo od njihovog kvadrata, međutim, ti kvadrati su već van tabele (jer su veći od 50), pa se postupak može završiti. Brojevi koji su ostali neprecrtani su prosti.
Precrtavanje brojeva modelovaćemo nizom (ili vektorom) koji sadrži logičke vrednosti (vrednosti tipa bool) i precrtane brojeve označavaćemo sa false, a neprecrtane sa true. Određivanje prostih brojeva (pomoću pomenutog niza tj. vektora) realizovaćemo u zasebnoj funkciji, jer ta funkcija može biti korisna i u mnogim narednim zadacima.
Recimo i da je bez obzira na to što su nama potrebni samo brojevi iz intervala od \(a\) do \(b\), u Eratostenovom situ potrebno vršiti analizu svih brojeva iz intervala od \(0\) do \(b\) (jer se precrtavanje mora vršiti i brojevima manjim od \(a\)).
// funkcija koja popunjava logicki niz podacima o prostim
// brojevima iz intervala [0, n]
void Eratosten(vector<bool>& prost, int n) {
// alociramo potreban prostor
prost.resize(n + 1, true);
prost[0] = prost[1] = false; // 0 i 1 nisu prosti
// brojevi ciji se umnosci precrtavaju
for (int i = 2; i * i <= n; i++)
// nema potrebe precrtavati umnoske slozenih brojeva
if (prost[i]) {
// precrtavamo umnoske broja i i to krenuvsi od i*i
for (int j = i * i; j <= n; j += i)
prost[j] = false;
}
}
// funkcija odredjuje broj i zbir po modulu 1000000 prostih
// brojeva iz intervala [a, b]
void prostiUIntevalu(int a, int b, int& broj, int& zbir) {
// odredjujemo proste brojeve u intervalu [0, b]
vector<bool> prost;
Eratosten(prost, b);
// analiziramo jedan po jedan broj u intervalu
zbir = 0; broj = 0;
for (int i = a; i <= b; i++)
if (prost[i]) {
zbir = (zbir + i) % 1000000;
broj++;
}
}#include <iostream>
#include <vector>
using namespace std;
// funkcija koja popunjava logicki niz podacima o prostim
// brojevima iz intervala [0, n]
void Eratosten(vector<bool>& prost, int n) {
// alociramo potreban prostor
prost.resize(n + 1, true);
prost[0] = prost[1] = false; // 0 i 1 nisu prosti
// brojevi ciji se umnosci precrtavaju
for (int i = 2; i * i <= n; i++)
// nema potrebe precrtavati umnoske slozenih brojeva
if (prost[i]) {
// precrtavamo umnoske broja i i to krenuvsi od i*i
for (int j = i * i; j <= n; j += i)
prost[j] = false;
}
}
// funkcija odredjuje broj i zbir po modulu 1000000 prostih
// brojeva iz intervala [a, b]
void prostiUIntevalu(int a, int b, int& broj, int& zbir) {
// odredjujemo proste brojeve u intervalu [0, b]
vector<bool> prost;
Eratosten(prost, b);
// analiziramo jedan po jedan broj u intervalu
zbir = 0; broj = 0;
for (int i = a; i <= b; i++)
if (prost[i]) {
zbir = (zbir + i) % 1000000;
broj++;
}
}
int main() {
// ucitavamo granice intervala
int a, b;
cin >> a >> b;
// odredjujemo broj i zbir po modulu 1000000 prostih brojeva iz
// intervala [a, b]
int broj, zbir;
prostiUIntevalu(a, b, broj, zbir);
// prijavljujemo rezultat
cout << broj << " " << zbir << endl;
return 0;
}Analiza složenosti je komplikovanija i zahteva određeno poznavanje teorije brojeva. Procenimo broj izvršavanja tela unutrašnje petlje. U početnom koraku spoljne petlje precrtava se oko \(\frac{n}{2}\) elemenata. U narednom, oko \(\frac{n}{3}\). U narednom koraku je broj \(4\) već precrtan, pa se ne precrtava ništa. U narednom se precrtava oko \(\frac{n}{5}\), nakon toga opet ništa, zatim \(\frac{n}{7}\) itd. U poslednjem koraku se precrtava oko \(\frac{n}{\sqrt{n}}\) elemenata. Dakle, broj precrtavanja je najviše
\[\frac{n}{2} + \frac{n}{3} + \frac{n}{5} + \ldots + \frac{n}{\sqrt{n}} = n \cdot \left( \sum_{\substack{d\ \mathrm{prost},\\ d \leq \sqrt{n}}} \frac{1}{d} \right)\]
Broj je zapravo i manji, jer prilikom precrtavanja u unutrašnjoj petlji precrtavanje ne krećemo od \(d\), već od \(d^2\), ali za potrebe lakšeg određivanja gornje granice složenosti koristićemo prethodnu ocenu.
Zbir \(H(m) = 1 + 1/2 + 1/3 + \ldots + 1/m = \sum_{d \leq m} \frac{1}{d}\) (takozvani harmonijski zbir) se asimptotski ponaša slično funkciji \(\log{m}\) (razlika između ove dve funkcije teži takozvanoj Ojler-Maskeronijevoj konstanti \(\gamma \approx 0.5772156649\)), pa samim tim znamo da taj zbir divergira. Kada se sabiranje vrši samo po prostim brojevima, tada se zbir ponaša kao logaritam harmonijskog zbira, tj. kao \(\log{\log{m}}\) (pa je i on divergentan). Dakle, u našem primeru možemo zaključiti da je broj precrtavanja jednak \(n \cdot \log{\log{\sqrt{n}}}\). Pošto je \(\log{\log{\sqrt{n}}} = \log{\log{n^{\frac{1}{2}}}} = \log{\left(\frac{1}{2}\log{n}\right)} = \log{\frac{1}{2}} + \log{\log{n}}\), pod pretpostavkom da je sabiranje brojeva (koje se koristi u implementaciji petlji) konstantne složenosti, važi da je složenost Eratostenovog sita \(O(n \cdot \log{\log{n}})\). Iako nije linearna, funkcija \(\log{\log{n}}\) toliko sporo raste, da se za sve praktične potrebe Eratostanovo sito može smatrati linearnim u odnosu na \(n\) (što je dosta sporije samo od ispitivanja da li je broj \(n\) prost, što ima složenost \(O(\sqrt{n})\), ali je brže od proveravanja svakog broja pojedinačno koje je složenosti \(O(n\sqrt{n})\)).
Napiši program koji određuje najveći zbir nekog segmenta (podniza uzastopnih elemenata) datog niza.
Sa standardnog ulaza se unosi broj \(n\) (\(1 \leq n \leq 50\,000\)), a zatim \(n\) celih brojeva između \(-10\) i \(10\), razdvojenih razmakom.
Na standardni izlaz ispiši traženi zbir.
6 2 -3 4 -1 3 -2
6
Segment najvećeg zbira je \(4, -1, 3\).
Najdirektniji mogući način da se zadatak reši je da se izračuna zbir svakog segmenta. Zbir svakog segmenta možemo izračunavati zasebno (u petlji ili bibliotečkom funkcijom). Efikasnije rešenje dobijamo ako segmente nabrajamo redom (ugnežđenim petljama, gde spoljašnja petlja nabraja redom leve, a unutrašnja desne krajeve segmenata) i zbir narednog segmenta izračunavamo inkrementalno, na osnovu zbira prethodnog segmenta.
U nastavku je prikazana implementacija algoritma u kom se zbir izračunava inkrementalno.
int maksZbirSegmenta(const vector<int>& a) {
int n = a.size();
int max = 0;
for (int i = 0; i < n; i++) {
int z = 0;
for (int j = i; j < n; j++) {
z += a[j];
if (z > max)
max = z;
}
}
return max;
}#include <iostream>
#include <vector>
using namespace std;
int maksZbirSegmenta(const vector<int>& a) {
int n = a.size();
int max = 0;
for (int i = 0; i < n; i++) {
int z = 0;
for (int j = i; j < n; j++) {
z += a[j];
if (z > max)
max = z;
}
}
return max;
}
int main() {
ios_base::sync_with_stdio(false);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
cout << maksZbirSegmenta(a) << endl;
return 0;
}Ako zbir svakog segmenta računamo nezavisno, sabiranjem njegovih elemenata (bilo u petlji, bilo pomoću bibliotečke funkcije), složenost rešenja je \(O(n^3)\). Ako zbirove segmenata računamo inkrementalno, dobijamo algoritam složenosti \(O(n^2)\). U oba slučaja elemente učitavamo u niz i memorijska složenost je \(O(n)\).
Algoritam zasnovan na proveri svih segmenata se slobodno može nazvati trivijalnim, jer se do njega dolazi prilično direktno i veoma jednostavno mu se i dokazuje korektnost i analizira složenost. Međutim, on je prilično neefikasan za rešavanje ovog problema, čak i kada se zbirovi računaju inkrementalno. Značajno unapređenje možemo dobiti kada primetimo da veliki broj segmenata uopšte ne moramo da obrađujemo, jer iz nekih drugih razloga znamo da njihov zbir ne može biti maksimalan.
Posmatrajmo niz -2 3 2 -3 -3 4 -2 5 -8 3 i zbirove svih njegovih nepraznih segmenata.
Prekid posle negativnog zbira
Razmotrimo bilo koji niz koji počinje negativnim brojem. Nijedan segment koji počinje tim brojem, ne može biti segment maksimalnog zbira, pošto se izostavljanjam tog broja dobija segment većeg zbira. Ovo svojstvo je i opštije. Ukoliko segment počinje prefiksom negativnog zbira, on ne može biti segment maksimalnog zbira, jer se izostavljanjem tog prefiksa dobija segment većeg zbira. Otud, pri inkrementalnom proširivanju intervala udesno, čim se ustanovi da je tekući zbir negativan, moguće je prekinuti dalje proširivanje i odmah preći na narednu narednu početnu poziciju (tj. narednu vrstu imajući u vidu sliku 14).
Na primer, čim vidimo da je prvi element prvog segmenta -2, možemo prekinuti dalju obradu elemenata prve vrste, jer će svi elementi druge vrste sigurno biti za dva veći nego odgovarajući elementi prve vrste (3 je veće od 1, 5 je veće od 3, 2 je veće od 0 itd.).
Slično, kada se prilikom proširivanja segmenta koji počinje na poziciji 1 (od elementa 3) dođe do toga da je parcijalni zbir -1 (što se dešava kada se izračuna zbir \(3+2-3-3=-1\), možemo prekinuti sa obradom daljih segmenata koji počinju na toj poziciji, jer smo sigurni da će za svaki od njih kasnije veći biti onaj koji se dobija izostavljanje prefiksa 3 2 -3 -3 (čiji je zbir -1). Zaista, od preostalih zbirova 3 1 6 -2 1 u drugoj vrsti za jedan su veći zbirovi -2 2 7 -1 2 u šestoj vrsti koji su dobijeni izostavljanjem tog prefiksa. Obratimo pažnju na to da prekid unutrašnje petlje na ovaj način uzrokuje da se maksimalna vrednost u tekućoj vrsti ne mora uopšte naći. Petlja koja obrađuje drugu vrstu će biti prekinuta čim se naiđe na zbir -1, kada je tekuća vrednost maksimuma 5 iako je maksimum te vrste 6. Sigurni smo da će u nekoj narednoj vrsti postojati veća vrednost od te najveće (zaista, u šestoj vrsti se javlja 7), pa nam nalaženje stvarnog maksimuma u tekućoj vrsti uopšte nije neophodno.
Iako se na ovaj način može preskočiti razmatranje nekih segmenata, u najgorem slučaju složenost nije smanjena. Na primer, u slučaju da su elementi niza strogo pozitivni, zbir nikad ne postaje negativan i složenost nakon ovog isecanja je i dalje kvadratne složenosti tj. \(O(n^2)\).
Odsecanje provere početaka unutar pozitivnog segmenta
Ako su svi elementi polaznog niza pozitivni, maksimalan zbir biva nađen za \(i=0\) i \(j=n-1\). Nakon toga se, uvećavanjem indeksa \(i\), zbir smanjuje pošto se svakim skraćivanjem segmenta sleva izostavlja neki pozitivan broj koji doprinosi zbiru. I ovo zapažanje se može uopštiti. Ne samo što je nepoželjno skratiti interval sleva za neki pozitivan broj, već je nepoželjno skratiti ga za bilo koji prefiks čiji je zbir pozitivan. Pitanje je dokle takvi prefiksi sežu? Bar do elementa čijim obuhvatanjem dobijamo prvi negativan prefiks. Otud segment maksimalnog zbira ne može počinjati ni na jednoj poziciji između tekuće početne pozicije i prve pozicije na kojoj zbir postaje negativan.
U navedenom primeru, maksimalni segment ne može počinjati na poziciji 2, jer se proširivanjem nalevo i dodavanjem elementa 3 sa pozicije 1 dobijaju sigurno zbirovi koji su veći za tri. Dakle, svi elementi druge vrste (koja odgovara poziciji 1 u nizu) su za 3 veći od odgovarajućih elemenata treće vrste (koja odgovara poziciji 2 u nizu). Zaista, 5 je veće od 2, 2 od -1 itd. Slično, ti elementi su za 5 veći od odgovarajućih elemenata četvrte vrste (koja odgovara poziciji 3 u nizu). Zaista, 2 je veće od -3, -1 od -6 itd. Oni su za 2 veći od odgovarajući elemenata pete vrste (koja odgovara poziciji 4 u nizu). Zaista, -1 je veće od -3, -3 je veće od -5 itd. Zato te tri vrste uopšte nema potrebe razmatrati.
Zahvaljujući ovom zapažanju, pri završetku obrade jedne vrste i prelasku na narednu, nije neophodno uvećavati promenljivu \(i\) za jedan, već je moguće nastaviti iza elementa čijim je uključivanjem zbir postao negativan.
Pošto se svaki element obrađuje samo jednom, prilikom implementacije nije neophodno sve elemente pamtiti u nizu.
int maksZbirSegmenta(const vector<int>& a) {
int n = a.size();
int max = 0;
int i = 0;
while (i < n) {
int z = 0;
int j;
for (j = i; j < n; j++) {
z += a[j];
if (z < 0)
break;
if (z > max)
max = z;
}
i = j + 1;
}
return max;
}#include <iostream>
#include <vector>
using namespace std;
int maksZbirSegmenta(const vector<int>& a) {
int n = a.size();
int max = 0;
int i = 0;
while (i < n) {
int z = 0;
int j;
for (j = i; j < n; j++) {
z += a[j];
if (z < 0)
break;
if (z > max)
max = z;
}
i = j + 1;
}
return max;
}
int main() {
ios_base::sync_with_stdio(false);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
cout << maksZbirSegmenta(a) << endl;
return 0;
}Primer 3.3.2. Na slici 14 je ilustrovan rad algoritma na primeru niza -2 3 2 -3 -3 4 -2 5 -8 3.
Na početku se promenljiva \(i\) inicijalizuje na \(0\) i kreće se sa obradom prve vrste. Zbir \(z\) se inicijalizuje na \(0\), a promenljiva \(j\) na vrednost promenljive \(i\), što je \(0\). Pošto već u prvom koraku unutrašnje petlje vrednost \(z\) postaje negativna (\(-2\)), unutrašnja petlja se prekida, i nakon toga se vrednost promenljive \(i\) postavlja na \(j+1=1\) (dakle, prelazi se na drugu vrstu). Ostali zbirovi prve vrste se ne izračunavaju (ovo odsecanje je opravdano jer oni odgovaraju segemntima koji počinjinju negativnom vrednošću \(-2\), pa se veći zbirovi mogu dobiti odbacivanjem te vrednosti).
Obrada elemenata druge vrste (\(i=1\)) počinje od pozicije \(j=i=1\). Promenljiva \(z\) se ponovo inicijalizuje na nulu, a zatim se uvećava za jedan po jedan element niza, sve dok joj vrednost ne postane negativna (što se prvi put dešava kada je \(j=4\) i tada je \(z=-1\)). Pri tom se u svakom koraku ažurira vrednost maksimuma \(z_{max}\) i on dostiže vrednost \(5\). Prekidom unutrašnje petlje preskočeno je računanje i analiziranje elemenata druge vrste iza vrednosti \(-1\) (što je opravdano, jer oni odgovaraju segmentima koji počinju prefiksom 3 2 -3 -3 čiji je zbir \(-1\) negativan). Nakon prekida unutrašnje petlje, vrednost promenljive \(i\) se postavlja na \(j+1=5\). To znači da se naredne tri vrste mogu preskočiti (u njima se nalaze zbirovi segmenata koji se od segmenta čiji se zbirovi nalaze u tekućoj vrsti dobijanjem izbacivanjem početnog pozitivnog prefiksa, pa su sigurno manji od njih).
Obrada elemenata šeste vrste (\(i=5\)) počinje od vrednosti \(j=i=5\). Promenljiva \(z\) se ponovo inicijalizuje na \(0\), i već nakon obrade prvog elementa (\(j=5\)) postaje negativna (\(-2\)). Nakon prekida unutrašnje petlje, promenljiva \(i\) se postavlja na vrednost \(j+1=6\).
Na kraju se obrađuje sedma vrsta (\(i=6\)). Promenljiva \(z\) se postavlja na nulu, a \(j\) na \(i=6\). Zbir \(z\) se zatim uvećava za jedan po jedan element i pošto ni u jednom trenutku ne postaje negativan stiže se do kraja niza (\(j=10\)). Tokom unutrašnje petlje ažurira se maksimum i dostiže vrednost \(9\). Po završetku unutrašnje petlje vrednost promenljive \(i\) se postavlja na \(j+1=11\) i spoljašnja petlja se završava. Izračunavanje vrednosti i analiza elemenata u poslednje tri vrste je opravdano preskočena.
Pošto obe promenljive prolaze kroz raspon od \(0\) do \(n\) i kreću se samo u jednom smeru (vrednost im se samo povećava i nikada ne smanjuje), složenost ovog rešenja je linearna tj. \(O(n)\). U prikazanoj implementaciji elementi se čuvaju u nizu pa je i memorijska složenost linearna tj. \(O(n)\), međutim, pošto se svaki element analizira samo jednom, za tim nema potrebe i moguće je napraviti i implementaciju konstantne memorijske složenosti.