حل رابطه بازگشتی

[veniz2008]

سلام دوستان،من دنبال راه حل تشریحی فرمول بازگشتی زیر هستم:
T(n) = aT(n/b) + cn*k ، البته جوابهای نهایی رو دارم ولی راه حلی برای حل کردنش نتونستم پیدا کنم،من به حل این مساله خیلی احتیاج دارم،تشکر از همکاری دوستان.

[shahmohammadi]

سلام. تو درس ساختمان داده حالت خاصي از اين رو به صورت T(n)=2T(n/2)+n
كه پيچيدگي مرتب سازي ادغام بود حل كرده بوديم . به صورت بسط حل مي شد.
براي حالت عموميش هم سه تاحالت بود.
حالا منظورتون رو از قسمت cn*k نميفهمم. كدوم يك ثابتن. سي يا كا.

[مسعود اقدسی فام]

سلام دوستان،من دنبال راه حل تشریحی فرمول بازگشتی زیر هستم:
T(n) = aT(n/b) + cn*k ، البته جوابهای نهایی رو دارم ولی راه حلی برای حل کردنش نتونستم پیدا کنم،من به حل این مساله خیلی احتیاج دارم،تشکر از همکاری دوستان.

به این قضیه اصطلاح قضیه اصلی حل روابط بازگشتی هم گفته می‌شه. بر اساس مقادیر a و b و k سه حالت مختلف پیش می‌یاد که جدا جدا قابل اثبات هستن.

[veniz2008]

ببینید دوستان،همانطور که دوستمون گفتن این قضیه اصلی است که در اون a,b,c,k اعداد ثابت هستن،وقتی به جای اینها عدد میذاریم(مثلا همون T(N)= 2T(N/2)+ n-1 که در واقع فرمول مرتب سازی ادغامی هست) به سادگی حل میشه چون در حین حل مساله فقط یکی از 3 حالت رو داریم(در واقع O(n^k*logn که چون k برابر با 1 هست جواب نهایی O(nlogn) میشه) ولی در حالت کلی به مشکل بر میخورم(هر کاری میکنم نمیتونم که هر 3 جواب رو بدست بیارم)،من از روش تغییر متغیر استفاده میکنم،در واقع : n =b^i میگیرم و با جایگذاری در مساله میخوام که حلش کنم ولی به جواب نمیرسم،لطفا دوستان راه حل عملی بگن،تشکر.

[shahmohammadi]

وقتي سي و كا هر دو ثابتن و مي شه اونا رو يه ثابت در نظر گرفت چه دليلي داره كه به اون شكل بنويسيم. من تو هر جا اينو ديدم يا يه ثابت داشته يا به صورت f(n) با ويژگي هايي كه داره نوشته. مي شه بگيد كه اين كار دليل خاصي داشته يا نه.

[مسعود اقدسی فام]

وقتي سي و كا هر دو ثابتن و مي شه اونا رو يه ثابت در نظر گرفت چه دليلي داره كه به اون شكل بنويسيم. من تو هر جا اينو ديدم يا يه ثابت داشته يا به صورت f(n) با ويژگي هايي كه داره نوشته. مي شه بگيد كه اين كار دليل خاصي داشته يا نه.

T(n) = aT(n/b) + cn^k درسته. یعنی n به توان k. جایگاه c و k فرق داره.

[veniz2008]

دوستان کسی جواب تشریحی این سوال رو نمیدونه؟؟:گریه::گریه:

[shahmohammadi]

با سلام دوباره.
می خواهیم رابطه ی T(N)=aT(n/b)+cn^k رو تشریحی حل کنیم.
برای سادگی n رو b^m می گیریم تا n/b عددی صحیح باشه.
ابتدا رابطه مذکور رو چندین بار بسط می دیم.

T(n)=a(aT(n/b^2)+c(n/b)^k)+cn^k
T(n)=a(a(aT(n/b^3)+c(n/b^2)^k)+c(n/b)^k)+cn^k

اگه عبارت رو اونقدر بسط بدیم که n/b^m برابر با 1 بشه خواهیم داشت:

T(n)=a(a(...T(n/b^m)+c(n/b^(m-1))^k)+...)+cn^k

اگر T(1) رو برابر با همون ثابت c مون بگیریم (هر مقدار دیگه ای نتیجه ی نهایی رو تنها به اندازه ی یک ضریب تغییر می ده) داریم:

ٰٰT(n)=ca^m + ca^(m-1)b^k + ca^(m-2)b^(2k) + ... + cb^(mk)



که سری زیر ازش نتیجه می شه:
74686
این مجموع یک تصاعد هندسی ساده است. (b^k/a) یا بزرگتر از یک هست یا برابر یا کوچکتر:

حالت اول: a>b^k
در این حالت ضریب تصاعد هندسی از یک کوچکتر است. پس سری به یک مقدار ثابت همگراست. بنابر این

T(n)=o(a^m)
m=log(n)
a^m=a^log(n)=n^log(a)
T(n)=O(n^loga)



حالت دوم: a=b^k
در این حالت ضریب تصاعد هندسی یک هست.

T(n)=O(ma^m)
a=b^k
loga=k
m=O(logn)
T(n)=O(n^klogn)


(در هر دو مورد لگاریتم ها پایه شون b هست)


حالت سوم: a<b^k
در این حالت، ضریب تصاعد هندسی بزرگتر از یک هست. b^k/a رو با q نمایش می دیم و a0 برابر با a^m هست پس داریم :
74688

پس فرمول زیر رو نتیجه می گیریم:
74690
که در اون a,b,c,k ثابت های صحیح هستند که a>=1 و b>=2 و c>0 و k>0 هست.