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

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



Юқоридаги ҳол каби муҳокама қиламиз. Дастлаб 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 да га еткач тўхтайди. Натижада ҳосил қиламиз