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

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 жуфт бўлса: