Подели па владај (информатика)
From Wikipedia, the free encyclopedia
У информатици, подели па владај је стратегија дизајнирања алгоритама заснована на рекурзији са вишеструким гранањем. Овакви алгоритми се заснивају на рекурзивном разлагању проблема на два или више подпроблема истог (или сличног) типа (подели), све док проблем не постане довољно једноставан да се може директно решити (владај). Решења тих подпроблема се након тога сједињавају и дају решење полазног проблема.
Ова стратегија је основа ефикасних алгоритама за решавање разноликих проблема, као што је проблем сортирања (нпр. Алгоритам брзог сортирања, Алгоритам сортирања обједињавањем, проблем множења великих бројева (нпр. Карацубин алоритам), проблем проналажења две најближе тачке, синтаксна анализа (нпр. анализа наниже и израчунавање дискретне Фуријеове трансформације.
Схватање и дизајн алгоритама заснованих на овој стратегији је сложена вештина која захтева добро разумевање природе проблема који треба да се реши, као што при доказивању теореме математичком индукцијом почетни проблем треба заменити општијим или компликованијим проблемом, како би се кренуло у рекурзивно решавање, при чему не постоји општи метод за проналажење праве генерализације. Овакве компликације се изражавају при оптимизацији израчунавања Фибоначијевог броја ефикасном двоструком рекурзијом.
Исправност алгоритама заснованих на разлагању се обично доказује математичком индукцијом, а сложеност израчунавања се одређује решавањем рекурентних једначина.