Подели па владај (информатика) — разлика између измена
Садржај обрисан Садржај додат
м додана категорија Оптимизациони алгоритми и методи помоћу геџета HotCat |
мНема описа измене |
||
Ред 1:
{{друго значење3|Podeli pa vladaj}}
'''Подели па владај''' ({{јез-лат|divide et impera}}) у [[информатика|информатици]] представља алгоритам у којем се већи проблем рашчлањује на више мањих, који су једноставнији за сагледавање и појединачно решавање.<ref name=CLR>-{Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, ''Introduction to Algorithms'' (MIT Press, 2000).}-</ref><ref>-{Brassard, G. and Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.}-</ref><ref>-{Anany V. Levitin, ''Introduction to the Design and Analysis of Algorithms'' (Addison Wesley, 2002).}-</ref> Ови потпроблеми се могу решавати паралелно (истовремено решавање два или више потпроблема) или један за другим. Овде се може издвојити неколико типова овог [[алгоритам|алгоритма]]:
* Решење последњег обрађиваног потпроблема је уједно и решење проблема. На пример, приликом претраживања уређеног [[бинарно стабло|бинарног стабла]] је тражени [[чвор (програмирање)|чвор]] управо чвор до кога се дошло при последњем извршеном кораку.
Ред 46:
Под условом да се сви потребни позиви могу паралелизовати, сложеност оваквог алгоритма је одређена висином нацртаног графа. Конкретно, пошто се низ стално дели на два дела, сложеност овог алгоритма при обради низа од ''-{n}-'' елемената ће бити ''-{O(log<sub>2</sub>n)}-'', што је мање од ''-{O(n)}-'', колико би износила сложеност линеарне претраге.
==Референце==
{{reflist}}
== Види још ==
| |||