ALGORITMI I STRUKTURE PODATAKA
V čas Algoritmi za rad sa nizovima i skupovima
Binarna i linearna pretraga niza
Takmičenje tri algoritma za sortiranje
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 x1, x2, ..., xn. 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 S1
za svako y iz skupa S1 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(n2)?
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 a1 a2 ... ak.
Označimo elemente drugog skupa posle sortiranja sa b1
b2 ....bn-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 ai + bj 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 ai + bj 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)