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

1.6. Рекуррент муносабатлар
Алгоритмнинг қийинлигига рекуррент муносабат бевосита алгоритмнинг шаклидан келиб чиқади, аммо унинг ёрдамида бу қийинликни тез ҳисоблаб бўлмайди. Бунинг учун рекуррент муносабатларни уларнинг рекуррентлик табиатини рад қилувчи ёпиқ шаклга келтириш талаб қилинади. Буларни бир қанча мисролларда тушунамиз.
Рекуррент муносабатлар икки шаклда берилади. Биринчиси камдан кам оддий ҳолларда ишлатилади:
Т(п) =2Т(n-2) - 15;
Т(2) =40;
Т(1) = 40.
Иккинчи шакли агар оддий ҳолатлар сони нисбатан катта бўлса ишлатилади:

Бу шакллар эквивалент. Иккинчисидан биринчисига барча оддий ҳолатлар рўйхатини ёзиб келиш мумкин. Бу шуни билдирадики, юқорида келтирилган рекуррент формулалардан иккинчисини қуйидаги шаклда ёзиш мумкин
T(п) = 4Т(n/2) - 1;
T(4) = 4;
T(3) = 4;
T(2) = 4;
T(1) = 4.
Қуйидаги рекуррент муносабатларни кўрамиз:
Т(п) =2Т(n-2) - 15;
Т(2) =40;
Т(1) = 40.
Биз биринчи тенгликни Т(п-2) учун эквивалент ифодага келтирмоқчимиз. Бунинг учун ундаги ҳамма n ни п – 2 билан алмаштирамиз:
Т(п- 2) = 2T(n - 2 - 2) - 15 = 2Т(n-4)-15.
Энди, T(n-4) қийматини чиқариб ташлашимиз керак. Худди шундай биз мос ўрин алмаштиришларни бажаришимиз керак. Буни катта бўлмаган кетма-кет қийматлар учун бажарамиз:
Т(n-2) = 2Т(n-4) - 15;
Т(п-4) = 2Т(n-6) - 15;
Т(n-6) = 2Т(n-8) - 15;
Т(n-8) = 2Т(n-10) - 15;
T(n-10) = 2Т(n-12) - 15.
Энди ҳисоблашлар натижаларини дастлабки тенгламаларга қўйиб чиқамиз. Бунда биз охиригача соддалаштириш бажармаймиз, чунки умумий схемани йўқотиб қўйишимиз мумкин. Қуйидагиларга эга бўламиз
T(n) = 2Т(n - 2) - 15 = 2(2Т(n - 4) - 15) - 15,
T(n) = 4Т(n-4)-2 • 15-15;
T(n) = 4(2Т(n - 6) - 15) - 2 • 15 - 15,
Т(n) = 8Т(n-6)-4 • 15-2 • 15-15;
T(n) = 8(2Т(n - 8) - 15) - 4 • 15 - 2 • 15 - 15,
T(n) = 16Т(n-8)-8 • 15-4 • 15-2 • 15- 15;
T(n) = 16(2Т(n - 10) - 15) - 8 • 15 - 4 • 15 - 2 • 15-15,
Т(n) = 32Т(n - 10) - 16 • 15 - 8 • 15 - 4 • 15 - 2 • 15-15;
T(n) = 32(2Т(n - 12) - 15) - 16 • 15-8 • 15 - 4 • 15 - 2 • 15-15,
T(n) = 64Т(n - 12) - 32 • 15 - 16 • 15 - 8 • 15 - 4 • 15 - 2 • 15-15.
Биринчи навбатда, ҳар бир тенгсизликдаги охиридан бошлаб қўшилувчилар ўзида иккининг навбатдаги даражаларига кўпайган -15 сонидан иборат. Иккинчидан, сезиш мумкинки, Т функция рекурсив чақилишидаги коэфициент иккининг даражаларидир. Бундан ташқари, Т функция аргументи ҳар сафар 2 га камаяди. Бу жараён қачон тугайди деб сўрашимиз мумкин. бошланғич тенгликка қайтиб эслаймизки, биз Т(1) ва Т(2) лар қийматини қайд қилгандик. Бу ўлчовларга етиб бориш учун нечта алмаштиришлар бажаришимиз керак? п жуфт бўлган ҳолда 2 = n - (n- 2) га эгамиз. Бу шуни билдирадики, биз (n - 2)/2 - 1 ўрин алмаштириш бажаришимиз керак, қайсики улар —15 кўпайтмали п/2-1 қўшилувчилар ва Т олдидан n/2 — 1 икки даражаларини беради. n = 14 да нима бўлишини текширамиз. Бу ҳолда, юқлридаги гапга кўра биз беш алмаштириш бажаришимиз керак; —15 кўпайтмали олтита қўшилувчига эга бўламиз ва Т(2) да коэфициент 2⁶ га тенг. Худди шундай натижа n = 14 да охирги тенглик орқали олинади.
Агар п тоқ бўлсачи? Шунда ҳам бу формулалар ишлайдими? п=13 қийматни қараймиз. Тенгликда битта ўзгариш, Т функция аргументи бўлиб 2 эмас 1 хизмат қилади, аммо n/2-1 қиймат 5 га (6 га эмас) тенг бўлади. п тоқ бўлганда n/2-1 ўрнига n/2 олишимиз керак. Демак, икки ҳолатни қарашимиз керак.
агар n жуфт бўлса:

агар n тоқ бўлса:


Энди (1.17) тенгликни қўллаб, жуфт n учун ҳосил қиламиз

n тоқ ҳолда эса

Яна бир рекуррентмуносабатни қараймиз:

Юқоридаги ҳол каби муҳокама қиламиз. Дастлаб n қийматини алмаштирамиз, бунда ҳар бир навбатдаги тенгликда олдинги аргументнинг ярми ҳосил бўлади. Натижада қуйидаги тенгликларга келамиз
T(n/2) = 4Т(n/4) - 1;
T(n/4) = 4Т(n/8) - 1;
Т(n/8) = 4T(n/16) - 1;
T(n/16) = 4Т(n/32) - 1;
Т(n/32) = 4Т(n/64) - 1.
Дастлабки тенгламаларга бу тенгликларни тескари алмаштиришлар қуйидагини беради:
Т(n) = 4T(n/2) - 1 = 4(Т(n/4) - 1) - 1,
Т(n) = 16Т(n/4) - 4•1-1;
Т(n) = 16(4Т(n/8) - 1) - 4 • 1 - 1,
T(n) = 64Т(n/8) - 16 • 1 - 4 • 1 - 1;
Т(n) = 64(Т(n/16) - 1) - 16 • 1 - 4 • 1-1,
Т(n) = 256Т(n/16) - 64 • 1 - 16 • 1 - 4 • 1 - 1;
T(n) = 256(4T(n/32) - 1) - 64 • 1 - 16 • 1-4•1-1,
T(n) = 1024Т(n/32) - 256 • 1 - 64 • 1 - 16 • 1 - 4 • 1-1;
Т(n)= 1024(4Т(n/64) - 1) - 256 • 1 - 64 • 1 - 16 • 1 - 4 • 1-1,
Т(n) = 4096Т(n/64) - 1024 • 1 - 256 • 1 - 64 • 1 - 16 • 1 - 4 • 1 - 1.
Кўриниб турибдики, –1 коэфициенти ҳар бир алмаштиришда тўрт баравар ўсади, аргументни бўладиган икки даражаси эса ҳар сафар тўртдан бир барвар катта. Т олдидаги тўрт даражаси коэфициент аргументни икки даражасига бўлганимиз каби. Бу коэфициент да га тенг, кейин – данто –1 гача қўшилувчилар кетади. i нинг қандай қийматида алмаштиришлар тўхтайди? Агар қиймат аниқ берилса n<4 да га еткач тўхтайди. Натижада ҳосил қиламиз

Энди аниқ қийматдан ва (1.18) тенгликдан фойдаланиб:





Кўриб турибсизки, рекуррент муносабат ёпиқ шаклда оддий эмас ва қўпол, аммо унга ўтиб рекурсив «чақирувдан» қутуламиз ва шу туфайли олинган ифодаларни тез солиштирамиз ва тартибини аниқлаймиз.