Ugnežđene petlje obično podrazumevaju da spoljašnja brojačka promenljiva stalno uvećava svoju vrednost tokom iteracije, dok se vrednost unutrašnje promenljive uvećava do neke gornje granice, zatim se ponovo vraća na neku donju granicu i to se ponavlja više puta. Ovo po pravilu dovodi do kvadratne složenosti (tj. složenosti višeg stepena u slučaju ugnežđavanja većeg broja petlji).
Tehnika dva pokazivača obuhvata široku klasu efikasnih algoritama koje takođe karakteriše postojanje dve ili više brojačkih promenljivih, koje se kreću kroz elemente nekog niza (često sortiranog). Međutim, ono što je karakteristično za njih je to što se, za razliku od unutrašnjih promenljivih u ugnežđenim petljama, ove promenljive stalno “kreću u istom smeru”, tj. vrednost im se ili stalno povećava ili stalno smanjuje (a česta je i kombinacija gde se “niz obilazi sa dva kraja”, gde se jedna promenljiva stalno povećava, a druga stalno smanjuje). Tehnička realizacija može biti bilo pomoću jedne petlje koja kontroliše vrednosti obe promenljive, bilo pomoću ugnežđenih petlji, ali tako da se nakon završetka tela unutrašnje petlje, spoljašnja promenljiva uvećava do mesta gde se unutrašnja petlja završila. Pošto se svaka promenljiva može promeniti najviše \(n\) puta (gde je \(n\) neko gornje ograničenje njihove vrednosti, obično dužina niza), broj promena (pa samim tim i izvršavanja tela petlje) je najviše \(2n\) i linearan je po \(n\) tj. složenost mu je \(O(n)\).
Algoritmi zasnovani na tehnici dva pokazivača obično mogu da se izvedu korišćenjem odsecanja primenjenih na ugnežđene petlje, pa je, kao zi kod svake primene odsecanja, potrebno pažljivo obrazložiti njihovu korektnost.
Tehnika pokretnog prozora je specijalni slučaj tehnike dva pokazivača u kojoj se oba pokazivača kreću sleva nadesno i ograničavaju segment niza koji se u tom trenutku obrađuje. Prozor može biti fiksne ili promenljive širine.
Pokažimo sada nekoliko najkarakterističnijih primena ove tehnike (nakon čega ćemo još nekoliko primena ilustrovati i kroz zadatke).
Ilustrujmo ovu tehniku na jednostavnom problemu preraspodeljivanja elemenata niza tako da se nakon preraspodele u nizu prvo nalaze elementi niza koji su manji ili jednaki datoj vrednosti \(x\) (u proizvoljnom redosledu), a zatim nalaze elementi niza koji su veći od date vrednosti \(x\) (u proizvoljnom redosledu). Videćemo u poglavlju 5.2 da je rešavanje ovog problema ključno za algoritam brzog sortiranja niza. Primetimo da za dati ulazni niz ne postoji jedinstveno rešenje (jer međusobni redosled elemenata u prvoj i u drugoj grupi može biti proizvoljan).
Jedno moguće rešenje može biti takvo da j pokazivač \(i\) ukazuje na naredni element niza koji treba obraditi, a da pokazivač \(j\), takav da važi \(j \leq i\) određuje granicu između elemenata manjih ili jednakih \(x\) i elemenata većih od \(x\). Preciznije, pretpostavićemo invarijantu koja tvrdi da su elementi na pozicijama u intervalu \([0, j)\) manji ili jednaki \(x\), elementi na pozicijama u intervalu \([j, i)\) veći od \(x\), dok su elementi na pozicijama u intervalu \([i, n)\) nepoznatog statusa.
| j | i | n | |||||||||
| \(\leq\) | \(\leq\) | \(\leq\) | \(>\) | \(>\) | \(>\) | \(>\) | ? | ? | ? | ? |
Na početku inicijalizujemo \(i=j=0\) i invarijanta važi.
Prilikom analize elementa na poziciji \(i\) mogu nastupiti dva slučaja.
int j = 0;
for (int i = 0; i < a.size(); i++)
if (a[i] <= x)
swap(a[i], a[j++]);Sasvim je jasno da je složenost ovog algoritma \(O(n)\).
Još jedno rešenje datog problema se može zasnovati na invarijanti da su svi elementi u intervalu \([0, i)\) manji ili jednaki \(x\), da su elementi u intervalu \((j, n)\) veći od \(x\), dok su elementi u intervalu \([i, j]\) još neobrađeni.
| i | j | n | |||||||||
| \(\leq\) | \(\leq\) | \(\leq\) | ? | ? | ? | ? | ? | \(>\) | \(>\) | \(>\) |
int n = a.size();
int i = 0, j = n-1;
while (i < j) {
while (i < j && a[i] <= x)
i++;
while (i < j && a[j] > x)
j--;
swap(a[i], a[j]);
}Na prvi pogled možda deluje da ova varijanta algoritma ima kvadratnu složenost, jer sadrži ungežđene petlje, međutim, to nije tačno. Naime, pošto se oba pokazivača kreću stalno u istom smeru (promenljiva i se samo uvećava, a promenljiva j umanjuje), kao i uvek u slučaju tehnike dva pokazivača, ukupan broj operacija je ograničen odozgo sa \(2n\) i složenost ovog algoritma je \(O(n)\).
Filtriranje podrazumeva da se iz niza izdvoje samo elementi koji zadovoljavaju neko svojstvo. Te elemente možemo premestiti u neki drugi niz, a možemo ih i zadržati u istom nizu, tako što ćemo ih pomeriti ka početku niza. Pokazivač i se može kretati redom kroz elemente niza, dok će pokazivač k označavati prvo trenutno slobodno mesto u nizu tj. broj elemenata koji su prebačeni na početak niza.
void izdvojParne(vector<int>& a) {
int k = 0;
for (int i = 0; i < a.size(); i++)
if (a[i] % 2 == 0)
a[k++] = a[i];
a.resize(k);
}Složenost prikazane funkcije je, očigledno, \(O(n)\), gde je \(n\) dužina niza.
Naivan način da se zadatak reši je da se elementi oba učitana niza prekopiraju u treći (bilo pomoću petlje, bilo bibliotečkom funkcijom copy) i da se onda sortiraju (najbolje bibliotečkom funkcijom sort). Kopiranje nizova dužine \(m\) i \(n\) zahteva \(m+n\) operacija, a sortiranje \(O((m + n)\cdot \log{(m + n)})\). Moguće je elemente odmah učitavati u rezultujući niz i tako uštedeti memoriju i vreme potrebno za kopiranje, ali dominatni faktor, a to je vreme potrebno za sortiranje bi ostao. Primetimo da u ovom rešenju nismo uopšte upotrebili činjenicu da su polazni elementi već sortirani.
Iako ovo rešenje po vremenu izvršavanja ne zaostaje puno u odnosu na optimalno (njegovo vreme izvršavanja je kvazilinearno, a optimalno vreme je linearno tj. \(O(m+n)\)), ono je komplikovanije nego što je potrebno. To se ne vidi kada se upotrebi bibliotečka funkcija sortiranja, međutim, implementacija efikasnog algoritma sortiranja zahteva napredne tehnike programiranja. Interesantno, jedan od popularnih algoritama sortiranja je sortiranje objedinjavanjem (engl. merge sort), opisan u poglavlju 5.1, u svom osnovnom koraku zahteva objedinjavanje dva sortirana niza u treći. Samim tim, donekle je besmisleno problem objedinjavanja rešavati svođenjem na komplikovaniji problem sortiranja.
Zadatak možemo rešiti efikasnim algoritmom, zasnovanom na tehnici dva pokazivača. Algoritam objedinjavanja (engl. merge) podrazumeva da su nizovi koji se objedinjavaju sortirani. Ako je jedan od nizova prazan, rezultat objedinjavanja je drugi niz i njegove elemente je potrebno jednostavno prekopirati u rezultat. Ako nizovi nisu prazni, pošto su sortirani, prvi element niza je ujedno najmanji u njemu. Manji od dva početna elementa je manji (ili jednak) od početnog elementa drugog niza, pa je manji ili jednak svim elementima u oba niza i samim tim je najmanji element od svih i treba da bude prvi u rezultatu. Kada se taj element ukloni iz niza, dobijamo problem istog tipa kao i polazni, koji se onda rešava na isti način.
Tokom iterativne implementacije održavaju se dva pokazivača: promenljiva \(i\) koja ukazuje na poziciju tekućeg elementa prvog i \(j\) koja ukazuje na tekući element drugog niza. Dok su obe ove promenljive manje od dužine niza po kojem se kreću, poredimo elemente na tim pozicijama, manji od njih prebacujemo u rezultujući niz i uvećavamo odgovarajući pokazivač. Kada bar jedan od pokazivača dostigne dužinu odgovarajućeg niza, tada elemente preostalog niza prepisujemo u rezultujući niz. Ne moramo eksplicitno proveravati da li u nekom od ovih nizova ima preostalih elemenata, već možemo u jednoj petlji kopirati preostale elemente prvog, a u drugoj petlji kopirati preostale elemente drugog niza (jedna od ovih petlji će biti prazna).
// objedinjava sortirani niz a sa n elemenata i sortirani niz b
// sa m elemenata smestajuci rezultat u sortirani niz c
vector<int> objedini(const vector<int>& a,
const vector<int>& b) {
int m = a.size(), n = b.size();
vector<int> c(m + n);
int i = 0, j = 0, k = 0;
while (i < n && j < m)
c[k++] = a[i] <= b[j] ? a[i++] : b[j++];
while (i < n)
c[k++] = a[i++];
while (j < m)
c[k++] = b[j++];
return c;
}#include <iostream>
using namespace std;
// objedinjava sortirani niz a sa n elemenata i sortirani niz b
// sa m elemenata smestajuci rezultat u sortirani niz c
vector<int> objedini(const vector<int>& a,
const vector<int>& b) {
int m = a.size(), n = b.size();
vector<int> c(m + n);
int i = 0, j = 0, k = 0;
while (i < n && j < m)
c[k++] = a[i] <= b[j] ? a[i++] : b[j++];
while (i < n)
c[k++] = a[i++];
while (j < m)
c[k++] = b[j++];
return c;
}
// najveci broj elemenata niza predvidjen tekstom zadatka
int main() {
ios_base::sync_with_stdio(false);
// ucitavamo prvi niz
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
// ucitavamo drugi niz
int m;
cin >> m;
vector<int> b(m);
for (int i = 0; i < m; i++)
cin >> b[i];
// objedinjavamo dva niza u treci
vector<int> c = objedini(a, n, b, m, c);
// ispisujemo rezultat
for (int i = 0; i < p; i++)
cout << c[i] << " ";
cout << endl;
return 0;
}Svaki pokazivač prolazi kroz jedan od dva niza i ukupan broj koraka je \(m+n\), pa je složenost ovog algoritma \(O(m+n)\).
U narednom apletu možete ispratiti primer rada ovog algoritma.
✖
U nastavku ćemo prikazati još nekoliko primera koji se efikasno rešavaju primenom tehnike dva pokazivača i pokretnog prozora.
Dat je ceo broj \(s\) i niz različitih celih brojeva. Napisati program kojim se određuje broj parova u nizu koji imaju zbir jednak datom broju \(s\).
U prvoj liniji standardnog ulaza nalazi se ceo broj \(s\) (broj iz intervala \([0, 10^6]\)), u drugoj liniji nalazi se broj elemenata niza \(n\) (\(1 \leq n \leq 50000\)), a u trećoj liniji se nalaze redom elementi niza (brojevi iz intervala \([0, 10^6]\)).
Na standardnom izlazu prikazati broj parova različitih elemenata niza čiji je zbir jednak broju \(s\).
5 6 1 4 3 6 -1 5
2
To su parovi \((1, 4)\) i \((6, -1)\).
Zadatak možemo rešiti tako što sortiramo niz neopadajuće (pošto su svi elementi različiti, on će zapravo biti sortiran strogo rastuće) i primenimo tehniku dva pokazivača, implementiranu iterativno.
Članove datog zbira možemo tražiti polazeći sa oba kraja niza. Obilazimo niz sa oba kraja: levog (\(l = 0\)) i desnog (\(d = n - 1\)). Uporedimo \(a_l + a_d\) sa \(s\).
Ako je \(a_l + a_d > s\) potrebno je smanjiti zbir para elemenata, što postižemo zamenom elementa manjim, pa pošto je niz sortiran u rastućem poretku, prelazimo na sledeći element u desnom delu niza (\(d\) umanjujemo za 1).
Ako je \(a_l + a_d < s\) potrebno je povećati zbir para elemanata, što postižemo zamenom elementa većim, pa pošto je niz sortiran u rastućem poretku, prelazimo na sledeći element u levom delu niza (\(l\) uvećavamo za 1).
Ako je \(a_l + a_d = s\) uvećamo broj traženih parova, i prelazimo na sledeći element u levom delu niza (\(l\) uvećavamo za 1) i na sledeći element u desnom delu niza (\(d\) umanjujemo za 1).
Proces nastavljamo dok ne obiđemo ceo niz, to jest dok je \(l < d\).
Primer 3.7.1. Prikažimo ovo na primeru pronalaženja elemenata čiji je zbir \(14\) u sortiranom nizu \(1, 2, 5, 7, 9, 11, 13, 14\). Krećemo od para \((1, 14)\). Pošto je zbir veći od traženog, pomeramo desni kraj ulevo i analiziramo par \((1, 13)\), koji ima traženi zbir. Zato prelazimo na \((2, 11)\). Pošto je zbir sada manji, pomeramo levi kraj udesno i analiziramo par \((5, 11)\). Zbir je preveliki i pomeramo desni kraj ulevo i analiziramo par \((5, 9)\). On ima traženi zbir, pa prelazimo na \((7, 7)\), no taj par ne analiziramo, jer su se pokazivači susreli.
int brojParovaDatogZbira(const vector<int>& a, int s) {
// pravimo sortiranu kopiju niza a
auto as = a;
sort(begin(as), end(as));
// brojimo parove pomocu dva pokazivaca
int brojParova = 0;
int levo = 0, desno = as.size() - 1;
while (levo < desno)
if (as[levo] + as[desno] > s)
desno--;
else if (as[levo] + as[desno] < s)
levo++;
else {
brojParova++;
levo++;
desno--;
}
return brojParova;
}#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int brojParovaDatogZbira(const vector<int>& a, int s) {
// pravimo sortiranu kopiju niza a
auto as = a;
sort(begin(as), end(as));
// brojimo parove pomocu dva pokazivaca
int brojParova = 0;
int levo = 0, desno = as.size() - 1;
while (levo < desno)
if (as[levo] + as[desno] > s)
desno--;
else if (as[levo] + as[desno] < s)
levo++;
else {
brojParova++;
levo++;
desno--;
}
return brojParova;
}
int main() {
ios_base::sync_with_stdio(false);
int s, n;
cin >> s >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
cout << brojParovaDatogZbira(a, s) << endl;
return 0;
}Pošto se u svakom koraku razlika između \(d\) i \(l\) smanji bar za 1 (nekada i za 2), ukupan broj koraka ne može biti veći od \(n\), pa je složenost ovog dela algoritma \(O(n)\). Naravno, složenošću dominira prvobitno sortiranje čija je složenost \(O(n\log{n})\).
Dat je niz \(a\) realnih brojeva dužine \(n\) i prirodan broj \(k\). Napisati program kojim se u nizu \(a\) određuje pozicija početka segmenta (podniza uzastopnih elemenata) dužine \(k\) sa najvećim prosekom (ako više segmenata ima isti prosek, prijaviti poslednji od njih).
U prvoj liniji standardnog ulaza nalazi se prirodan broj \(k\) (\(k\leq 5 \cdot 10^3\)). U drugoj liniji nalazi se prirodan broj \(n\) (\(n \leq 5\cdot 10^5\)). U sledećih \(n\) linija nalaze se po jedan realan broj (ti brojevi predstavljaju redom elemente niza \(a\)).
Na standarnom izlazu prikazati poziciju početka poslednjeg segmenta dužine \(k\) niza \(a\) čiji je prosek najveći (pozicije u nizu se broje od nule).
3 5 1.0 5.0 8.0 2.0 7.0
2
Segment najvećeg proseka je 8, 2, 7 i on počinje na poziciji 2 u nizu.
Primetimo da je problem nalaženja segmenta dužine \(k\) čiji je prosek najveći, ekvivalentan problemu nalaženja segmenta dužine \(k\) najvećeg zbira. Prosek segmenta dobijamo deljenjem sume segmenta sa dužinom segmenta, koja je u ovom zadatku konstanta i iznosi \(k\), tako da je prosek najveći kada je zbir najveći.
Pošto se uzastopni segmenti u velikoj meri preklapaju (razlikuju im se samo početni i završni element) zadatak se može rešavati inkrementalno, tehnikom pokretnog prozora. pristup, u kojem se zbir narednog segmenta dužine \(k\) (tzv. prozora) računa na osnovu poznatog zbira prethodnog segmenta dužine \(k\). Ako sa \(S_i\) obeležimo zbir segmenta koji počinje od elementa \(a_i\) i dužine je \(k\), \(S_i = a_i + a_{i+1} + ... + a_{i+k-1}\), lako se može pokazati da za \(i > 0\) važi jednakost \(S_i = S_{i-1}- a_{i-1} + a_{i+k-1}\). Prema tome možemo izračunati zbir \(S_0\) kao zbir prvih \(k\) elemenata niza (opet uobičajenim algoritmom sabiranja), a zatim za svako \(i\) od \(1\) do \(n-k\) naredni zbir \(S_i\) dobijamo na osnovu prethodne jednakost.
// pronalazi indeks pocetka segmenta duzine k ciji je prosek najveci
int pocetakSegmentaNajvecegProseka(const vector<double>& a, int k) {
// duzina niza
int n = a.size();
// suma pocetnog segmenta duzine k
double suma = 0;
for (int i = 0; i < k; i++)
suma += a[i];
// trenutna maksimalna suma segmenta i indeks njenog pocetka
int maxPocetak = 0;
double maxSuma = suma;
for (int i = 1; i <= n - k; i++) {
// izracunavamo sumu segmenta duzine k koji pocinje na poziciji i
suma = suma - a[i - 1] + a[i + k - 1];
// ako je potrebno, azuriramo maksimum
if (suma >= maxSuma) {
maxSuma = suma;
maxPocetak = i;
}
}
// vracamo pocetak poslednjeg segmenta sa maksimalnom sumom
// (ujedno i prosekom)
return maxPocetak;
}#include <iostream>
#include <vector>
using namespace std;
// pronalazi indeks pocetka segmenta duzine k ciji je prosek najveci
int pocetakSegmentaNajvecegProseka(const vector<double>& a, int k) {
// duzina niza
int n = a.size();
// suma pocetnog segmenta duzine k
double suma = 0;
for (int i = 0; i < k; i++)
suma += a[i];
// trenutna maksimalna suma segmenta i indeks njenog pocetka
int maxPocetak = 0;
double maxSuma = suma;
for (int i = 1; i <= n - k; i++) {
// izracunavamo sumu segmenta duzine k koji pocinje na poziciji i
suma = suma - a[i - 1] + a[i + k - 1];
// ako je potrebno, azuriramo maksimum
if (suma >= maxSuma) {
maxSuma = suma;
maxPocetak = i;
}
}
// vracamo pocetak poslednjeg segmenta sa maksimalnom sumom
// (ujedno i prosekom)
return maxPocetak;
}
int main() {
ios_base::sync_with_stdio(false);
// ucitavamo podatke
int n, k;
cin >> k >> n;
vector<double> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
// ispisujemo rezultat
cout << pocetakSegmentaNajvecegProseka(a, k) << endl;
return 0;
}U svakom koraku petlje vrši se samo konstantan broj operacija, pa je složenost algoritma linearna tj. \(O(n)\). Elementi se čuvaju u nizu dužine \(n\), pa je memorijska složenost \(O(n)\).