TechCodeview

Завади па владај је алгоритамски образац. У алгоритамским методама, дизајн је да се узме спор о великом улазу, разбије улаз на мање делове, реши проблем на сваком од малих делова, а затим споји решења по комадима у глобално решење. Овај механизам решавања проблема назива се стратегија завади и владај.

Алгоритам Завади па владај састоји се од спора који користи следећа три корака.

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

Генерално, можемо пратити завади па владај приступ у процесу од три корака.

Примери: Специфични компјутерски алгоритми су засновани на приступу Завади и владај:

1. Максимални и минимални проблем
2. Бинарно претраживање
3. Сортирање (разврставање спајањем, брзо сортирање)
4. Ханојска кула.

Основе стратегије завади и владај:

Постоје две основне стратегије Завади и владај:

1. Релациона формула
2. Стопинг Цондитион

1. Релациона формула: То је формула коју генеришемо из дате технике. Након генерисања формуле примењујемо Д&Ц стратегију, тј. рекурзивно разбијамо проблем и решавамо покварене подпроблеме.

2. Услов заустављања: Када решимо проблем користећи стратегију Завади и владај, онда морамо да знамо колико времена треба да применимо Завади и владај. Дакле, услов у коме је потреба за заустављањем наших рекурзивних корака Д&Ц назива се услов заустављања.

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

Следећи алгоритми су засновани на концепту технике завади и владај:

Бинарна претрага:Алгоритам бинарне претраге је алгоритам претраживања, који се такође назива претрага у полуинтервалу или логаритамска претрага. Ради тако што упоређује циљну вредност са средњим елементом који постоји у сортираном низу. Након поређења, ако се вредност разликује, онда ће половина која не може да садржи циљ на крају елиминисати, након чега следи наставак претраге на другој половини. Поново ћемо размотрити средњи елемент и упоредити га са циљном вредношћу. Процес се наставља све док се не постигне циљна вредност. Ако смо након завршетка претраге открили да је друга половина празна, онда се може закључити да циљ није присутан у низу.Брзо сортирање:То је најефикаснији алгоритам за сортирање, који је такође познат као сортирање разменом партиција. Почиње тако што се изабере пивот вредност из низа након чега следи дељење остатка елемената низа у два подниза. Партиција се прави упоређивањем сваког од елемената са пивот вредношћу. Он упоређује да ли елемент има већу или мању вредност од пивота, а затим рекурзивно сортира низове.Сортирање спајањем:То је алгоритам за сортирање који сортира низ вршењем поређења. Почиње дељењем низа на подниз, а затим рекурзивно сортира сваки од њих. Након што се сортирање заврши, спаја их назад.Најближи пар тачака:То је проблем рачунарске геометрије. Овај алгоритам наглашава проналажење најближег пара тачака у метричком простору, датих н тачака, тако да растојање између пара тачака треба да буде минимално.Штрасенов алгоритам:То је алгоритам за множење матрице, који је добио име по Фолкеру Штрасену. Показало се да је много бржи од традиционалног алгоритма када ради на великим матрицама.Цоолеи-Тукеи алгоритам брзе Фуријеове трансформације (ФФТ):Алгоритам брзе Фуријеове трансформације назван је по Ј. В. Цоолеиу и Џону Турчију. Следи приступ Завади па владај и намеће сложеност О(нлогн).Каратсуба алгоритам за брзо множење:То је један од најбржих алгоритама за множење традиционалног времена, који је изумео Анатолиј Карацуба крајем 1960. и објављен 1962. Он множи два н-цифрена броја на такав начин тако што их своди на највише једноцифрена.

Предности Завади па владај

• Завади па владај има тенденцију да успешно реши један од највећих проблема, као што је торањ у Ханоју, математичка слагалица. Изазов је решавати компликоване проблеме за које немате основну идеју, али уз помоћ приступа завади па владај, то је умањило напор јер ради на подели главног проблема на две половине, а затим их решава рекурзивно. Овај алгоритам је много бржи од других алгоритама.
• Ефикасно користи кеш меморију без заузимања много простора јер решава једноставне подпроблеме унутар кеш меморије уместо да приступа споријој главној меморији.
• Она је вештија од своје колеге Бруте Форце технике.
• Пошто ови алгоритми инхибирају паралелизам, он не укључује никакве модификације и њиме управљају системи који укључују паралелну обраду.

Недостаци Завади па владај

• Пошто је већина његових алгоритама дизајнирана укључивањем рекурзије, тако да је потребно високо управљање меморијом.
• Експлицитни стек може претерано искористити простор.
• Може чак и да сруши систем ако се рекурзија изврши ригорозно већа од стека присутног у ЦПУ-у.