Rešitev: Poišči največji in najmanjši element v tabeli

Iz MaFiRaWiki

Naloga: Poišči največji in najmanjši element v tabeli

Algoritem

Algoritem bomo poiskali s pomočjo metode deli in vladaj. Problem bomo torej razdelili na manjše podprobleme, ki jih znamo enostavno rešiti, nato pa rešitev sestavili iz rešitev manjših problemov.

Če je tabela dolžine 2, je večji element maksimum, manjši minimum. Sicer tabelo razpolovimo. Sedaj imamo dve tabeli (levo in desno). Za vsako od njiju moramo najti največji in najmanjši element. Ko dobimo najmanjši element leve tabele, ga ozničimo z mL, največjega z ML, na desni strani pa simetrično mD in MD. Rezultat je min = min{mL,mD} in max = max{ML,MD}. mL, mD, ML in MD dobimo tako, da tabelo še naprej razpolavljamo, dokler ne dobimo tebele dolžine 2. V taki je minimum manjši element, maksimum pa večji.

Časovna zahtevnost

Naj bo n = 2k dolžina tabele, T(n) pa časovna zahtevnost.

T(2) = 1, ker za tabelo dolžine 2 rabimo eno primerjanje.

Recimo, da vemo, koliko je T(\frac{n}{2}). Ko smo našli minimum in maksimum leve in desne polovice tabele (vsak del je dolg \frac{n}{2}, zato potrebujemo 2T(\frac{n}{2}) operacij), moramo poiskati še minimum med mL in mD oz. maksimum med ML in MD. To sta še dve primerjanji.

Torej smo dobili rekurzivno enačbo za časovno zahtevnost: T(n)=2T(\frac{n}{2})+2. Začetni pogoj je T(2) = 1.

Če izračunamo T(n) za nekaj začetnih n-jev, dobimo:

n T(n)
1 1
2 1
4 4
8 10
16 22

Uganem formulo T(n)=\frac{3}{2}n-2.

To dokažemo z indukcijo:

  • n=2 (k=1): 1=T(2)=\frac{3}{2} \cdot 2-2
  • 2^k \rightarrow 2^{k+1}: T(2^{k+1})=2 \cdot (\frac{3}{2} \cdot 2^k -2)+2=(\frac{3}{2} \cdot 2^{k+1}-4)+2=\frac{3}{2} \cdot 2^{k+1} -2
Osebna orodja