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

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



бунда DAC — DivideAndConquer алгоритми қийинлиги,
DIR — DirectSolution алгоритми қийинлиги,
DIV — DivideInput алгоритми қийинлиги,
COM —CombineSolutions алгоритми қийинлиги.
Ушбу умумий формуланинг мавжудлиги бошда қўйилган саволга осон жавоб беради. Биз фақат ҳар бир қисмдаги маълум қийинликларни умумий формулага қўйсак бас. Натижада қуйидагига эга бўламиз

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

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