Подијели и освоји алгоритам

У овом упутству ћете научити како функционише алгоритам подели и освоји. Такође ћемо упоредити приступ подели и победи са осталим приступима за решавање рекурзивног проблема.

Алгоритам завади па владај је стратегија за решавање великог проблем

разбијање проблема на мање под-проблеме
решавање под-проблема и
комбинујући их да би се добио жељени излаз.

Да би се користио алгоритам подели и освоји, користи се рекурзија . Сазнајте о рекурзији на различитим програмским језицима:

Рекурзија на Јави
Рекурзија у Питхону
Рекурзија у Ц ++

Како функционишу алгоритми за поделу и освајање?

Ево следећих корака:

Подјела : Подијелите задати проблем на под-проблеме помоћу рекурзије.
Освајање : Решавајте мање под-проблеме рекурзивно. Ако је потпроблем довољно мали, решите га директно.
Комбиновање: Комбинујте решења потпроблема који су део рекурзивног процеса да бисте решили стварни проблем.

Разумимо овај концепт помоћу примера.

Овде ћемо сортирати низ користећи приступ дели и освоји (тј. Спајање сортирај).

Нека дати низ буде: Низ за сортирање спајањем
Поделите низ на две половине. Поделите низ на два поддела
Поново поделите сваки поддео рекурзивно на две половине док не добијете појединачне елементе. Поделите низ на мање подделове
Сада комбинирајте појединачне елементе на сортирани начин. Овде освајајте и комбинујте кораке један поред другог. Комбинујте подделове

Сложеност времена

Сложеност алгоритма подели и освоји израчунава се помоћу главне теореме.

Т (н) = аТ (н / б) + ф (н), где је, н = величина улаза а = број потпроблема у рекурзији н / б = величина сваког потпроблема. Претпоставља се да сви подпроблеми имају исту величину. ф (н) = цена посла обављеног изван рекурзивног позива, који укључује трошкове поделе проблема и трошкове обједињавања решења

Узмимо пример да бисмо пронашли временску сложеност рекурзивног проблема.

За сортирање спајања, једначина се може записати као:

 Т (н) = аТ (н / б) + ф (н) = 2Т (н / 2) + О (н) Где је а = 2 (сваки пут је проблем подељен у 2 потпроблема) н / б = н / 2 (величина сваког потпроблема је половина улаза) ф (н) = време потребно за поделу проблема и спајање потпроблема Т (н / 2) = О (н лог н) (Да бисте ово разумели, погледајте главна теорема.) Сада је Т (н) = 2Т (н лог н) + О (н) ≈ О (н лог н)

Дивиде анд Цонкуер Вс Динамички приступ

Приступ подели и освоји освоји дели проблем на мање потпроблеме; ови подпроблеми се даље решавају рекурзивно. Резултат сваког потпроблема се не чува за будућу референцу, док се, у динамичком приступу, резултат сваког потпроблема чува за будућу референцу.

Користите приступ подели и освоји када исти подпроблем није решен више пута. Користите динамички приступ када ће се резултат потпроблема у будућности користити више пута.

Разумимо ово на примеру. Претпоставимо да покушавамо да пронађемо Фибоначијеву серију. Онда,

Приступ подели и освоји:

 фиб (н) Ако је н <2, врати 1 Елсе, врати ф (н - 1) + ф (н -2)

Динамички приступ:

 мем = () фиб (н) Ако је н у мем: вратити мем (н) елсе, Ако је н <2, ф = 1 елсе, ф = ф (н - 1) + ф (н -2) мем (н) = ф повратак ф

У динамичком приступу мем меморише резултат сваког потпроблема.

Предности алгоритма за поделу и освајање

Сложеност множења две матрице применом наивне методе је О (н ³ ), док је коришћење дељења и освајања (тј. Страссеново умножавање матрице) О (н ^2.8074 ). Овај приступ такође поједностављује друге проблеме, попут Ханојске куле.
Овај приступ је погодан за вишепроцесорске системе.
Ефикасно користи меморијске кеш меморије.