ALGORITMI I STRUKTURE PODATAKA

V čas Algoritmi za rad sa nizovima i skupovima

Stablo odlučivanja definiše se kao binarno stablo sa dve vrste čvorova, unutrašnjiim čvorovima i listovima. Svaki unutrašnji čvor odgovara pitanju sa dva moguća odgovora, koji su pak pridruzeni dvema granama koje izlaze iz čvora. Svakom listu pridružen je jedan od mogućih izlaza.

Gde se koristi ovo stablo? Stablo odlučivanja modelira izračunavanja koja se sastoje najvećim delom od upoređivanja. Koriste se kao model u dokazu da je donja granica složenosti svakog algoritma za sortiranje zasnovanog na poređenju Ω(n log n)

Neka se sortira ulazni niz x₁, x₂, ..., x_n. Izračunavanje počinje od korena stabla. U svakom čvoru postavlja se jedno pitanje u vezi sa ulazom, i u zavisnosti od dobijenog odgovora, nastavlja se levom ili desnom izlaznom granom. Kad se dostigne list, izlaz pridružen listu je izlaz izračunavanja.

Na slici gore prikazano je sortiranje pomocu stabla odlučivanja za n = 3. Vremenska složenost (u najgorem slučaju) algoritma definisanog stablom T jednaka je visini stabla T, odnosno najvecem mogucem broju pitanja koja treba postaviti za neki ulaz. Stablo odlučivanja prema tome odgovara algoritmu.

1. Dat je skup S od n realnih brojeva i realan broj x. Konstruisati algoritam složenosti Ω (n log n) koji utvrđuje da li u S postoje dva elementa kojima je zbir jednak x.

Rešenje:

sortirati skup S i neka je rezulat S₁
za svako y iz skupa S₁ binarnom pretragom tražiti član jednak sa brojem x-y

U opisanom algoritmu dominantan broj koraka potiče od koraka broj 1, čija donja granica složenosti je Ω (n log n) za algoritme sortiranja zasnovane na upoređivanjima.

Kako biste resili zadatak ako je skup S sortiran u rastucem poretku? Kolika bi bila vremenska slozenost konstruisanog resenja ?

2. Dat je skup S od n realnih brojeva. Konstruisati algoritam složenosti O(n) koji pronalazi broj koji nije u S

Rešenje:

Taj broj može biti broj za jedan veći od najvećeg broja u skupu S.
Max svih brojeva se može naći jednim prolazom kroz skup S tako što se inicijalno postavi da je jednak 1. članu, a potom se prelazi kroz svaki sledeći član skupa i ukoliko je tekući član veći od max do tada, onda se promenljiva max ažurira i dobija vrednost tekućeg člana skupa S.

Kako se kroz skup S prolazi tačno jednom i za svaki član obavljaju operacije poređenja sa promenljivom max i eventualna ažuriranja njene vrednosti (što je const vreme), onda je ukupna vremenska složenost O(n).

Algoritam manje slo ženosti ne može da rešava problem za svaki ulaz, jer ne može da pregleda svih n članova skupa S.

3. Neka je E zadati niz brojeva x[0], x[1],..., x[n-1]. Višestrukost broja x u E je broj pojavljivanja x u E. Odrediti element E višestrukosti veće od n/2 ("preovlađujući element") ili ustanoviti da takav ne postoji.

na primer: 2 3 2 5 5 5 5 2 5 1 5 4 5 = > 5 je preovlađujući

Ideja 1 : izvrši se sortiranje, te ako postoji preovlađujući broj, on je u sredini i izvrši se za njega provera pozicije u sortiranom nizu. Može li efikasnije?

Ideja 2: Odrediti medijanu (videti u knjizi poglavlje o rangovskim statistikama - medijana je n/2-ti najmanji element), te je nađen kandidat za proveru. Može li efikasnije od O(n²)?

PODSEĆANJE: Formulacija problema rangovskih statistika: Za zadati niz elemenata S sa n članova i broj k, 0 <= k < n, odrediti k-ti najmanji elemenat u S. Kao i kod sortiranja razdvajanjem, loš izbor pivota vodi kvadratnom algoritmu.

Ideja 3: Ako je x[i] različito od x[j] i ako se izbace oba ova elementa iz niza, onda ako postoji y koji je preovlađujući element starog niza, onda je on preovlađujući element i novog niza (obratno ne važi).

U algoritmu se u jednom prolazu koriste promenljive C, M, gde C je jedini kandidat za preovlađujući element u nizu x[0],x[1],..,x[i-1].
M je broj pojavljivanja elementa C u nizu x[0], x[1],...,x[i-1], bez onih elemenata C koji su izbačeni.

Ako je x[i]==C, onda se M uvećava za 1, a inače smanjuje za 1. (tada se smatra da x[i] može biti izbačen zajedno sa nekim članom jednakim C).
Ako M postane 0, onda C dobije novu vrednost x[i] i time i M postane 1.

Algoritam Preovladjuje (x,n):
ulaz: x, n /* niz pozitivnih brojeva x, dimenzije n*/
izlaz: preovlada /* preovladjujuci alaement (ako postoji) ili -1 */

C=x[0];
M=1;
for(i=1; i < n; i++)
if (M==0)
{C=x[i]; M=1;}
else
if (x[i]==C) M++; else M--;

if (M==0) preovlada=-1; /*nema preovladjujuceg elementa*/
else brojac=0;

for (i=0; i < n; i++)
if (x[i]==C) brojac++;

if (brojac > n/2) preovlada=C; else preovlada=-1;

4. Data su dva skupa realnih brojeva S1 i S2 i realni broj x. Ustanoviti da li postoje realni brojevi y1 iz S1 i y2 iz S2 takvi da im je zbir jednak x. Vremenska složenost algoritma treba da bude O(n log n), gde je n ukupan broj elemenata u oba skupa.

REŠENJE:

Neka u prvom skupu ima k, a u drugom n-k elemenata.

1. Sortirajmo oba skupa u rastucem redosledu i označimo elemente prvog skupa posle sortiranja sa a₁ a₂ ... a_k.
Označimo elemente drugog skupa posle sortiranja sa b₁ b₂ ....b_n-k

2. Za svako i takvo da 1 <= i <= n - k: niz a1 + bi, a2 + bi, . . . , ak + bi je rastući, te se
binarnom pretragom pomocu O(log n) (preciznije [log k]+1) upoređivanja među ovim brojevima
pronalazi x, ili se utvrđuje da ni jedan od njih nije jednak x.

Znači, za proveru svih parova a_i + b_j dovoljno je O(n log n) upoređivanja

SLOŽENOST algoritma:
složenost početnog sortiranja u koraku 1 je O(n log n)
za proveru svih parova a_i + b_j u koraku 2 dovoljno je O(n log n) upoređivanja,

te je ukupna složenost algoritma O(n log n).

5 Kutije su numerisane redom od 1 do n, gde je n paran broj.U i-toj kutiji je smeštena količina od a[i] objekata. Konstruisati algoritam koji će spojiti sadržaje po dve kutije, ali tako da maksimalna količina objekata u po dve kutije bude što je moguće manja.

Rešenje:

sortirati niz a i rezultat je niz b
formirati parove (b[1],b[n]), (b[2], b[n-1]),..., (b[i], b[n-i+1]), i <= n/2

Dokaz korektnosti postupka:
=> dokaz da ma koje spajanje sadržaja po dve kutije različito od spajanja iz koraka 2, ima max količinu u po dve kutije ne manju od dobijene maksimalne količine u koraku 2

Pretpostavimo suprotno, tj. uočimo spajanje sadržaja po dve kutije koje umesto para (b[1], b[n]) ima parove(b[1], b[i]), (b[j], b[n])
Ako ta dva para se zamene parovima (b[1], b[n]), (b[i], b[j]), onda zbog (*), (**) se ne uvećava max zbirova, gde važi da:
(*) b[1]+b[n] <= b[j] + b[n]
(**) b[i]+b[j] <= b[j] + b[n]
Slično, ako se iz rezulatata koraka 2, umesto para (b[i], b[n-i+1]), i = 1 . . n/2
koriste drugi parovi,onda se opet n/2 puta primeni diskusija slična kao za (*), (**) uz zaključak da svih n/2 premeštanja parova imaju povećanje maksimuma zbirova => parovi (b[1],b[n]), (b[2], b[n-1]),..., (b[i], b[n-i+1]), i <= n/2, su optimalno rešenje zadatka.

6. Dat je niz od n prirodnih brojeva sa više ponavljanja elemenata, tako da je broj različitih elemenata u nizu O(log n).

a) Konstruisati algoritam za sortiranje ovakvih nizova, u kome se izvršava najviše O(n log log n) upoređivanja brojeva.
b) Zašto je složenost ovog algoritma manja od donje granice Ω(n log n) za sortiranje?

REŠENJE:

a) Svaki element niza umetnuće se kao jedno polje čvora balansiranog binarnog stabla pretrage. Drugo polje čvora će čuvati broj pojava tog elementa u nizu. Ako je broj različitih elemenata u nizu O(log n), onda je broj čvorova u stablu O(log n),
te je visina stabla O(log log n) => broj upoređivanja je najviše O(n log log n).

Zatim se stablo obilazi inorder obilaskom i njegovi elemeenti se kopiraju u neopadajućem redosledu u izlazni niz dužine n tako što se svaki element kopira onoliko puta kolika je vrednost odgovarajućeg brojačkog polja.

b) Opisani algoritam pod a) nije obuhvaćen modelom stabla odlučivanja, jer je pri konstrukciji algortma bilo od značaj da postoji relativno mali broj različitih elemenata u nizu, tj. vrednosti elemenata niza su bile značajne.

7. Dat je hip sa n elemenata tako da najveći element je u korenu. Dat je i realan broj x. Konstruisati algoritam koji samo utvrđuje da li je k-ti najveći element hipa manji ili jednak od x. Nije nužno odrediti k-ti najveći element hipa. Vremenska složenost algoritma mora da (nezavisno od veličine hipa) bude O(k). Dozvoljeno je koristiti memorijski prostor veličine O(k) (u slučaju da se koristi rekurzija, dozvoljeno je koristiti memorijski prostor veličine O(k) za pamćenje rekurzivnih poziva, tj. za stek).

k-ti najveći element hipa veći od x <=> postoji k elemenata hipa koji su veći od x, k >= 0

broj=0; /* promenljiva koja cuva broj elemenata vecih od x; ova promenljiva mora ziveti, tj. cuvati vrednost izmedju rekurzivnih poziva,
te je staticka ili globalna ili ...*/

odgovor=NE; /* odgovor da li je k-ti najveći element hipa manji ili jednak od x */

Algoritiam Utvrdi (Hip H sa korenom v, x, k)
ulaz: H, k, x
izlaz: odgovor DA/NE

{
if (!v) return ODGOVOR;
if (v->vrednost > x) broj++;

if (broj > k) return (odgovor==DA);

Utvrdi(H sa korenom v->prviSin, x,k);

Utvrdi(H sa korenom v->drugiSin, x,k);

}

Bez obzira na veličinu hipa, broj rekurzivnih poziva f-je Utvrdi je O(k), jer algoritam se rekurzivno spušta niz hip H i uvećava promenljivu broj sve dok se ne prođe ceo hip H ili se ne izbroji k elemenata. Za pamćenje rekurzivnih poziva potrebno je koristiti stek, tj. memorijski prostor O(k)