Подели па владај

Основни механизам конструкције алгоритама је тзв. индуктивно-рекурзивна конструкција где се решење проблема своди на решавање потпроблема истог облика, али мање димензије. Веома често је димензија потпроблема за један мања од димензије оригиналног проблема. На пример, низ се разлаже на свој први елемент и низ елемената иза њега (суфикс) или се разлаже на елементе који претходе последњем елементу (префикс) и тај последњи елемент. На пример, у алгоритму сортирања селекцијом (selection sort) на прво место се поставља најмањи елемент низа, а затим се на исти начин обрађују елементи иза њега, док се у алгоритму сортирања уметањем (insertion sort) сортира префикс низа у који се на крају умеће последњи елемент. Ови алгоритми су описани у задатку Сортирање бројева. Осим решавања потпроблема, алгоритам обично садржи кораке потребне да се потпроблем припреми и кораке да се од резултата потпроблема добију резултати полазног проблема. На пример, у алгоритму сортирања селекцијом припремни корак је одређивање позиције минимума и његово довођење на почетак низа, док је у алгоритму сортирања уметањем након обраде поптпроблема (сортирања префикса) додатни корак уметање последњег елемента. Ако се, као што је то случај у ова два примера, обрада потпроблема врши било као први или као последњи корак алгоритма (ако не постоји фаза припреме или обраде резултата потпроблема), тада имплементација може бити и итеративна.

• Ако се решава један потпроблем и ако се припрема потпроблема и обрада резултата потпроблема врше у времену \(O(1)\), уз уобичајену претпоставку да се излаз из рекурзије такође врши у времену \(O(1)\), време решавања задовољава једначину \(T(n) = T(n-1) + O(1), T(0) = O(1)\), чије је решење \(T(n) = O(n)\).

• Ако се решава један потпроблем и ако се припрема потпроблема и обрада резултата потпроблема врше у времену \(O(n)\), уз уобичајену претпоставку да се излаз из рекурзије такође врши у времену \(O(1)\), време решавања задовољава једначину \(T(n) = T(n-1) + O(n), T(0) = O(1)\), чије је решење \(T(n) = O(n^2)\).

Ефикаснија решења се често добијају техником која се назива техника разлагања, техника декомпозиције или техника подели-па-владај (енгл. divide-and-conquer). Њена основна идеја је то да је често ефикасније решавати неколико потпроблема чија је димензија два (или више) пута мања од димензије полазног потпроблема. Таквих проблема може бити два или више. Код изразито једноставних проблема решење је могуће добити и решавањем само једног таквог потпроблема, чиме се добијају изразито ефикасна решења.

Основни примере технике разлагања су сортирање обједињавањем (енгл. merge sort) и брзо сортирање (енгл. quick sort). И ови су алгоритми описани у задатку Сортирање бројева. Такође, алгоритми обраде бинарног дрвета спадају у ову групу (јер су поддрвета потпроблеми који су у случају балансираних дрвета два пута мањи од димензије полазног проблема). Бинарна претрага се такође може убројати у алгоритам овог типа, али, пошто се код ње један потпроблем потпуно занемарује (примењује се одсецање), та техника се понекад назива смањи па владај (енгл. decrease and conquer).

Ако су потпроблеми који се решавају једнаке димензије (два пута мање од димензије полазног проблема), добија се нека од следећих једначина (у зависности од тога колико времена је потребно за припрему потпроблема и обједињавање резултата добијених потпроблема). Решења једначина овог типа се могу често добити применом мастер теореме, а ми ћемо у наставку резимирати само неколико најкарактеристичнијих.

• Једначина \(T(n) = 2T(n/2) + O(n)\), \(T(0) = O(1)\) има решење \(O(n \log{n})\).

• Једначина \(T(n) = 2T(n/2) + O(1)\), \(T(0) = O(1)\) има решење \(O(n)\).

• Једначина \(T(n) = 2T(n/2) + O(\log{n})\), \(T(0) = O(1)\) има решење \(O(n)\).

• Једначина \(T(n) = 2T(n/2) + O(n\log{n})\), \(T(0) = O(1)\) има решење \(O(n\log^2(n))\).

Треба обратити пажњу на то да ако су потпроблеми стално неравномерне димензије, могуће је да се добије процес који се дегенерише у процес који се описује једначином \(T(n) = T(n-1) + O(n)\), \(T(0) = O(1)\) и чије је решење \(O(n^2)\) (што је, на пример, сложеност најгорег случаја у алгоритму quick sort, ако пивот

У случају алгоритама типа decrease and conquer, решава се само један потпроблем и добијају се најчешће једначине следећег типа.

• Једначина \(T(n) = T(n/2) + O(n)\), \(T(0) = O(1)\) има решење \(O(n)\).

• Једначина \(T(n) = T(n/2) + O(1)\), \(T(0) = O(1)\) има решење \(O(\log{n})\).