(۱۹ آبان ۱۳۹۱ ۱۱:۴۱ ق.ظ)nasi1391 نوشته شده توسط:  

(19 آبان ۱۳۹۱ ۱۱:۰۶ ق.ظ)reimei نوشته شده توسط:  سلام؛
در جواب تحلیل پیچیدگی این عبارت بازگشتی:
[tex]T(n) = T(n/5) log^2n[/tex]
نوشته:
[tex]T(n) = O(log^3(n))[/tex]
ولی راه حلش رو ننوشته. لطفا راهنمایی بفرمایید.
با تشکر

با قضیه مستر حل میشود. ولی برای یادگیری و تمیرین بیا تغییر متغییر بدیمٰ، بجای n بزاریم پنج به توان k در نتیجه :
[tex]T(5^k)=T(5^(k-1)) (log(5^k))^3=T(5^(k-1)) k^3[/tex]
حال بیا تغییر متغییر بدیهم : یعنی بجای تابع : [tex]T(5^k)[/tex] بزاریم : [tex]g(k)[/tex]
در نتیجه داریم : g(k)=g(k-1)+k^3 که یه رابطه بازگشتی ناهمگنه چون جمله ای [tex]k^3[/tex] داره.
خوب حالا بیا معادله مشخصه این رابطه همگن رو بدست بیاریم : [tex](r-1)(r-1)^4=0[/tex]
در نتیجه [tex]g(k)=c_1(1)^k c_2k(1)^k c_3k^2(1)^k c_4k^3(1)^k \epsilon O(k^3)[/tex]
و ببعد از تغییر تابع و تغییر متغییر داریم : [tex]T(n)=T(5^k)=g(k)=K^3 , k=log(5^k)=log(n) , T(n)=log(n)^3[/tex]