Подели па владај (информатика)
Из пројекта Википедија
Један од најстаријих закона „подели па владај“ (лат: divide et impera, још и „завади па владај“) примењив је на многе сфере људског живота и свакодневне проблеме и задатке. Због своје универазлности нашао је широку примену и у информатици.
[уреди] Алгоритми
Сам принцип алгоритамске примене се одражава на смањењу алгоритамске сложености проблема његовим разлагањем на коначан број потпроблема који се могу паралелно (истовремено) или секвенцијално (један за другим) решавати. Решавањем ових потпроблема, решава се и проблем који они чине. Ово се може спровести на више начина:
- Решење последњег потпроблема је истовремено и решење проблема. На пример, приликом претраживања бинарног стабла је тражени чвор управо чвор до кога се дошло при последњем извршеном кораку.
- Решење проблема се добија међусобним повезивањем решења подпроблема. На пример, приликом сортирања низа помоћу quick-sort низ се сортира током целог процеса. Завршетак последњег корака озвачава да је низ сортиран, али цео низ није нужно сортиран само у том кораку.
- Решење проблема се добија бирањем једног од решења подпроблема према одређеним условима. На пример, приликом тражења потпростора који испуњава одређене услове у датом простору је битно да уколико решења има више, буде изабрано оно које је за даљи рачун најпогодније.
