У овом упутству ћете научити како функционише алгоритам подели и освоји. Такође ћемо упоредити приступ подели и победи са осталим приступима за решавање рекурзивног проблема.
Алгоритам завади па владај је стратегија за решавање великог проблем
- разбијање проблема на мање под-проблеме
- решавање под-проблема и
- комбинујући их да би се добио жељени излаз.
Да би се користио алгоритам подели и освоји, користи се рекурзија . Сазнајте о рекурзији на различитим програмским језицима:
- Рекурзија на Јави
- Рекурзија у Питхону
- Рекурзија у Ц ++
Како функционишу алгоритми за поделу и освајање?
Ево следећих корака:
- Подјела : Подијелите задати проблем на под-проблеме помоћу рекурзије.
- Освајање : Решавајте мање под-проблеме рекурзивно. Ако је потпроблем довољно мали, решите га директно.
- Комбиновање: Комбинујте решења потпроблема који су део рекурзивног процеса да бисте решили стварни проблем.
Разумимо овај концепт помоћу примера.
Овде ћемо сортирати низ користећи приступ дели и освоји (тј. Спајање сортирај).
- Нека дати низ буде:
Низ за сортирање спајањем - Поделите низ на две половине.
Поделите низ на два поддела
Поново поделите сваки поддео рекурзивно на две половине док не добијете појединачне елементе.
Поделите низ на мање подделове - Сада комбинирајте појединачне елементе на сортирани начин. Овде освајајте и комбинујте кораке један поред другог.
Комбинујте подделове
Сложеност времена
Сложеност алгоритма подели и освоји израчунава се помоћу главне теореме.
Т (н) = аТ (н / б) + ф (н), где је, н = величина улаза а = број потпроблема у рекурзији н / б = величина сваког потпроблема. Претпоставља се да сви подпроблеми имају исту величину. ф (н) = цена посла обављеног изван рекурзивног позива, који укључује трошкове поделе проблема и трошкове обједињавања решења
Узмимо пример да бисмо пронашли временску сложеност рекурзивног проблема.
За сортирање спајања, једначина се може записати као:
Т (н) = аТ (н / б) + ф (н) = 2Т (н / 2) + О (н) Где је а = 2 (сваки пут је проблем подељен у 2 потпроблема) н / б = н / 2 (величина сваког потпроблема је половина улаза) ф (н) = време потребно за поделу проблема и спајање потпроблема Т (н / 2) = О (н лог н) (Да бисте ово разумели, погледајте главна теорема.) Сада је Т (н) = 2Т (н лог н) + О (н) ≈ О (н лог н)
Дивиде анд Цонкуер Вс Динамички приступ
Приступ подели и освоји освоји дели проблем на мање потпроблеме; ови подпроблеми се даље решавају рекурзивно. Резултат сваког потпроблема се не чува за будућу референцу, док се, у динамичком приступу, резултат сваког потпроблема чува за будућу референцу.
Користите приступ подели и освоји када исти подпроблем није решен више пута. Користите динамички приступ када ће се резултат потпроблема у будућности користити више пута.
Разумимо ово на примеру. Претпоставимо да покушавамо да пронађемо Фибоначијеву серију. Онда,
Приступ подели и освоји:
фиб (н) Ако је н <2, врати 1 Елсе, врати ф (н - 1) + ф (н -2)
Динамички приступ:
мем = () фиб (н) Ако је н у мем: вратити мем (н) елсе, Ако је н <2, ф = 1 елсе, ф = ф (н - 1) + ф (н -2) мем (н) = ф повратак ф
У динамичком приступу мем меморише резултат сваког потпроблема.
Предности алгоритма за поделу и освајање
- Сложеност множења две матрице применом наивне методе је О (н 3 ), док је коришћење дељења и освајања (тј. Страссеново умножавање матрице) О (н 2.8074 ). Овај приступ такође поједностављује друге проблеме, попут Ханојске куле.
- Овај приступ је погодан за вишепроцесорске системе.
- Ефикасно користи меморијске кеш меморије.
Поделите и освојите апликације
- Бинарна претрага
- Сортирање спајањем
- Брзо сортирање
- Множење матрице Страссен
- Каратсуба алгоритам
