Подели па владај (информатика)

Из Википедија

Подели па владај (лат. divide et impera, код нас такође познат и као „завади па владај“) је један од најстријих закона. Применљив је на многе сфере људског живота, свакодневне проблеме и задатке, због своје чега је нашао широку примену и у информатици.

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

Решење подследњег обрађиваног потпроблема је уједно и решење проблема. На пример, приликом претраживања уређеног бинарног стабла је тражени чвор управо чвор до кога се дошло при последњем извршеном кораку.
Решење проблема се добија међусобним повезивањем решења потпроблема. На пример, квиксорт сортира низ тако што га подели на два делимично уређена низа, а потом сваки од њих настави уређивати на исти начин. По завршетку последњег корака низ је сортиран, но није све сортирање нужно обављено само у том кораку.
Решење проблема се добија бирањем једног од решења потпроблема према одређеним условима. На пример, приликом тражења потпростора који испуњава одређене услове у датом простору је битно да, уколико решења има више, буде изабрано оно које је за даљи рачун најпогодније.

[уреди] Примери

[уреди] Максимална вредност низа

Рецимо да је дат низ a = {2,3,-2,5,12,15,100,22,-5} чију максималну вредност треба наћи. Рекурзивно решење по овом принципу би гласило:

Претпозив:
0. Позови алгоритам max за низ a, у његовим целокупним границама l и r.

Алгоритам:
1. Уколико је l > r, завршило се са претрагом низа или га није ни било.
   Врати најмању могућу вредност.
2. Уколико је l = r, дошло се до тога да више нема елемената за
   поређење. Врати или a[l] или a[r].
3. Уколико је разлика између l и r само 1, упоредити a[l] и a[r]
   и вратити већи од њих.

4. У осталим случајевима одредити једно пивот место p = (l+r)/2 и позвати овај
   алгоритам два пута:
      а. За низ a у границама l и p
      б. За низ a у границама p+1 и r

   Резултате оба позива упоредити и вратити већи број.

Поједностављење које се постиже овим алгоритмом је да се увек пореде два или врати само један преостали број тј. када низ има дужину већу од 2, у једном позиву алгоритма се не пореде сви елементи. Следи шематски приказ на коме се може видети на који начин алгоритам дели и обрађује низ:

Легенда:

- Прослеђене границе (под)низова

- Враћени максимуми (под)низова

- Нумерација поднизова

Треба приметити да се обрада поднизова I и VI може паралелизовати, јер би се радило о позивима истог алгоритма над два подниза. Ови позиви не морају да знају ишта о другим позивима, већ само да позиву у коме су позвани врате своје резултате које ће он обрадити.

Под условом да се сви потребни позиви могу паралелизовати, сложеност оваквог алгоритма је одређена висином нацртаног графа. Конкретно, пошто се низ стално дели на два дела, сложеност овог алгоритма при обради низа од n елемената ће бити O(log₂n), што је мање од O(n), колико би износила сложеност линеарне претраге.