Мундарижа Кириш

1.5. «Бўлаклаш ва бошқариш» шаклидаги алгоритмлар

Юқорида таъкидлаганимиздек, «бўлаклаш ва бошқариш» шаклидаги алгоритмлар турли масалаларни ечишда ихчам ва кучли восита бўлиб ҳисобланади. Уш бу бўлимда биз нафақат бундай алгоритмларни тузиш билан, балки уларнинг таҳлили билан ҳам шуғулланамиз. Циклдаги солиштиришларни ҳисоблашда бизга циклнинг бир итерациясидаги солиштиришларни ҳисоблаш кифоя ва уларни итерациялар сонига кўпайтирамиз. Ушбу ҳисоб агар ички цикл итерациялари сони ташқи цикл параметрларига боғлиқ бўлса мураккаблашади.

«Бўлаклаш ва бошқариш» шаклидаги алгоритмлардаги итерацияларни ҳисоблаш осон эмас, яъни у бошланғич ва якунловчи ҳаракатлардан, рекурсив чақурувлардан боғлиқ. Одатда рекурсив чақирувларда у ёки бу функция неча марта бажарилиши ноаниқ бўлади. Мисол сифатида қуйидаги алгоритмни қараймиз.

DivideAndConquer(data,N,solution)
data кирувчи маълумотлар тўплами

N тўпламдаги қийматлар сони

solution масала ечими

if (N <= SizeLimit) then

DirectSolution(data,N,solution)

else

DivideInput(data,N,smallerSets,smallerSizes,numberSmaller)

for i=l to numberSmaller do

DivideAndConquer(smallerSets[i],smallerSizes[i],smallSol[i])

end for

CombineSolutions(smallSol,numberSmaller,solution)

end if

Бу алгоритм дастлаб масала ўлчами кичик эмаслигини, яъни ечимни оддий но рекурсив (DirectSolution деб номланган) алгоритм ёрдамида ечиш мумкин бўлган ҳолни текширади, агар шундай бўлса у ҳолда у чақирилади. Агар масала жуда катта бўлса, у ҳолда дастлаб кирувчи маълумотларни бир қанча (уларнинг сони numberSmaller га тенг) кичик тўпламларга ажратувчи Dividelnput процедураси чақирилади. Бу кичик тўпламларнинг барча бир хил ўлчамли ёки жиддий фарқ қилиши мумкин. бошланғич кирувчи тўпламдаги ҳар қайси элемент ҳеч бўлмаганда кичик тўпламлардан бирига тушади, аммо бир элемент бир қанча тўпламларга тушиши ҳам мумкин. Кейин ҳар бир кичик тўпламларда DivideAndConquer алгоритм рекурсив чақирилади, CombineSolutions функция эса олинган натижаларни бир натижага олиб келади.

Натурал соннинг факториалини циклда ҳисоблаш қийин эмас, аммо қуйидаги мисолда бизга бу ҳисоблашнинг рекурсив варианти зарур бўлади. N сонининг факториали N нинг N – 1 сон факториалига кўпайтмасига тенг. Шу сабабли кейинги алгоритм қўл келади:

Factorial(N)

N сон,бизга керак бўлган факториал

Factorial бутун сонга эга бўлади
if (N=1) then

return 1

else

smaller = N-1

answer=Factorial(smaller)

return (N*answer)

end if

Ушбу алгоритмнинг қадамлари оддий ва тушунарли ва биз уни юқоридаги стандарт алгоритм билан солиштиришимиз мумкин. Юқорида таъкидлаганимиздек кўпайтириш амали қўшиш амалига қараганда мураккаброқ, шунинг учун кўпайтиришни алоҳида ҳисоблаш керак. Мисолни соддалаштириш учун бу фарқни ҳисобга олмаймиз.

Ушбу икки алгоритмларни таққослашда кўриниб турибдики бизнинг ҳолда маълумотларнинг сўнгги ўлчами 1 ва бундай маълумотларда ҳеч қандай арифметик амаллар бажарилмайди. Қолган барча ҳолларда else қисмга келамиз. Умумий алгоритмнинг биринчи қадамида «киришларни кичик қисмларга ажратиш» бажарилади; факториални ҳисоблаш алгоритмида эса бу қадамга битта айиришни талаб қилувчи ўзгарувчи smaller ни ҳисоблаш мос келади. Умумий алгоритмнинг кейинги қадами кичик маълумотларни қайта ишловчи процедурани рекурсив чақириш ташкил этади; факториални ҳисоблаш алгоритмида бу битта рекурсив чақирув ва масала ўлчами аввалгисидан 1 га кам. Умумий алгоритмнинг охирги қадами ечимларни бирлаштириш бўлса, факториални ҳисоблаш алгоритмида бу охирги return операторидаги кўпайтиришдир.

Рекурсив алгоритмнинг самарадорлиги

Рекурсив алгоритм қанчалик самарадор? Агар алгоритм бевосита ҳисобланиши квадратик, кирувчи маълумотларнинг ажратилиши логарифмик, ечимларни бирлаштириш чизиқли (барчаси кирувчи малумотларнинг ўлчамига боғлиқ равишда) эканлигини билсак унинг самарадорлигини ҳисоблай оламизми ва кирувчи маълумотлар ҳар бири бошланғич маълумотларнин чорагига тенг саккиз қисмга ажратилган бўлсачи? Ушбу масалани ҳал қилиш осон эмас, ҳатто унга қандай киришиш ҳам тушунарсиз. Аммо «бўлаклаш ва бошқариш» шаклидаги алгоритмлар таҳлили агар сизнинг алгоритмингиз юқоридаги умумий алгоритмнинг қадамларига мос бўлса, яъни бевосита ҳисоблаш, киришни бўлиш, бир қанча рекурсив чақирувлар ва олинган ечимларни бирлаштиришлар мавжуд бўлса жуда осон. Агар бу қадамлар бир-бири билан қандай тузилганлиги ва ҳар бир қадам қийинлиги маълум бўлса, у ҳолда «бўлаклаш ва бошқариш» шаклидаги алгоритмлар қийинлигини аниқлаш учун қуйидаги формуладан фойдаланиш мумкин:

бунда DAC — DivideAndConquer алгоритми қийинлиги,

DIR — DirectSolution алгоритми қийинлиги,

DIV — DivideInput алгоритми қийинлиги,

COM —CombineSolutions алгоритми қийинлиги.

Ушбу умумий формуланинг мавжудлиги бошда қўйилган саволга осон жавоб беради. Биз фақат ҳар бир қисмдаги маълум қийинликларни умумий формулага қўйсак бас. Натижада қуйидагига эга бўламиз



ёки соддароқ қилиб барча кичик тўпламлар тенг бўлганда:



Бу шаклдаги тенглик рекурруент формула дейилади, яъни унинг қиймати ўз шакли билан ифодаланган. Биз мураккабликнинг фақат N га боғлиқ ифодасини топишни ҳоҳлаймиз ва бошқа шу фунцияларни чақирувчиларга боғлиқ бўлмасин. Бу ҳақда реккурент боғланишлар батафсил ўрганиладиган § 1.6 бўлимда берилган.

Факториал мисолига қайтамиз. Биз факториални ҳисобловчи алгоритмнинг барча босқичларини умумий алгоритм DivideAndConquer билан таққосладик. Энди ушбу таққослашдан фойдаланамиз ваюқорида келтирилган умумий формулага келувчи қийматларни аниқлаймиз. Натижада биз қуйидаги Factorial функциянинг ҳисоблашлар сонининг реккурент боғланишига эга бўламиз:



1.5.1. Рекурсияга асосланган усуллар

Мусобақа усули рекурсияга асосланган ва у ёрдамида маълумотлардан биринчи ўтиш кейинги ўтишларни осонлаштирувчи турли масалаларни ечиш мумкин. агар биз уни энг катта қийматни топишга қўлласак, у ҳолда барча элементлари барг бўлган бинар дарахтни қуришни талаб қилади. Ҳар бир даражада икки элемент бир жуфтга бирлашган ва икки элементдан каттаси ота-она тугунга кўчирилади. Жараён илдиз тугунга етгунга қадар қайтарилади. Белгиланган маълумотлар тўплами учун тўлиқ мусобақа дарахти 1.3 расмда тасвирланган.

1.3-расм. Саккиз қийматли тўплам учун мусобақа дарахти

Мусобақа усули ёрдамида қийматлар тўпламини ҳам саралаш мумкин. Кейинги бўлимларда бизга мусобақа усулига асосланган тўдаларни саралаш учрайди.