Kompyuter injiniringi ” fakulteti “dasturiy injiniring” kafedrasi

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

бу ерда DAC —DivideAndConquer алгоритм мураккаблиги,

DIR —Direct Solution алгоритм мураккаблиги,
DIV —Divide Input алгоритм мураккаблиги,
COM —CombineSolutions алгоритм мураккаблиги.

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

ёки, барча кичик тўпламлар ҳажми бир хил бўлганлиги учун бундан ҳам осонроқ усули:

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