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

Из Википедије, слободне енциклопедије
Disambig.svg
За остале употребе, погледајте чланак Podeli pa vladaj.

Подели па владај (лат. divide et impera) у информатици представља алгоритам у којем се већи проблем рашчлањује на више мањих, који су једноставнији за сагледавање и појединачно решавање.[1][2][3] Ови потпроблеми се могу решавати паралелно (истовремено решавање два или више потпроблема) или један за другим. Овде се може издвојити неколико типова овог алгоритма:

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

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

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

Нека је дат низ 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 и позвати овај исти
   алгоритам два пута:
      1. За низ a у границама од l до p
      2. За низ a у границама од p+1 до r

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

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

Array maximum - divide et impera.png

Легенда:

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

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

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

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

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

Референце[уреди]

  1. ^ Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, Introduction to Algorithms (MIT Press, 2000).
  2. ^ Brassard, G. and Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.
  3. ^ Anany V. Levitin, Introduction to the Design and Analysis of Algorithms (Addison Wesley, 2002).

Види још[уреди]