Deli in vladaj

tehnika reševanja problemov, kjer glavni problem razbijes na manjše podprobleme, ki jih rešuješ

neodvisno od glavnega, iz njihovih rešitev pa sestaviš rešitev glavnega problema,

V praksi so ti podproblemi ponavadi enaki glavnemu, resujemo jih lahko rekurzivno z enakim algoritmom,

ki kliče samega sebe.

Formula za izračun časovne zahtevnosti glavnega problema pa je:

T(n)=b pri n=1

sicer

a* T(n/c) + f(n),

kjer je funcija f(n) čas razbitja/sestavljanja delnih rešitev skupaj ter je v praksi polinomska oblike

b*n^r, kjer je b pač neka konstanta...

Ker je natačna rešitev rekurivne enačbe T(n) "preveč" natančna, jo lahko opišemo glede na asimptotično

vedenje in sicer a, c in r:

a= število podproblemov ki jih moramo izračunat, c pa število vseh podproblemov... r pa je tista potenca

polinoma za časovni zahtevnost razbitja/sestavljanja.

Pol pa mamo tiste 3 primere(Master theorem):

a<c^r T(n)=O(n^r)---polinomski čas

a=c^r T(n)=O(n^r*logn)---- log-polinomski čas

a>c^r T(n)=O(n^(logc(a)))------eksponentni

Primeri: Quicksort, iskanje k, binarno iskanje, Strauss, Rekurzini DFT