سلام؛
در جواب تحلیل پیچیدگی این عبارت بازگشتی:
[tex]T(n) = T(n/5) log^2n[/tex]
نوشته:
[tex]T(n) = O(log^3(n))[/tex]
ولی راه حلش رو ننوشته. لطفا راهنمایی بفرمایید.
با تشکر
(۱۹ آبان ۱۳۹۱ ۱۱:۰۶ ق.ظ)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))^2=T(5^(k-1)) k^2[/tex]
حال بیا تغییر متغییر بدیهم : یعنی بجای تابع : [tex]T(5^k)[/tex] بزاریم : [tex]g(k)[/tex]
در نتیجه داریم : g(k)=g(k-1)+k^2 که یه رابطه بازگشتی ناهمگنه چون جمله ای [tex]k^2[/tex] داره.
خوب حالا بیا معادله مشخصه این رابطه همگن رو بدست بیاریم : [tex](r-1)(r-1)^3=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]
(۱۹ آبان ۱۳۹۱ ۱۱:۴۱ ق.ظ)nasi1391 نوشته شده توسط:خیلی ممنون از پاسختون، ولی اینجا چرا [tex](log(5^k))^3[/tex] شد؟ روی سوال که [tex]log^2n[/tex] هست.(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]
میشه لطفا حل این سوال رو با قضیه اصلی هم توضیح بدین.
خوب این درست شد :
![[تصویر: 142650_1_1379088001.gif]](https://img.manesht.ir/142650_1_1379088001.gif)
بی زحمت یکم تشکر کنید
(۱۹ آبان ۱۳۹۱ ۰۴:۰۰ ب.ظ)farhadk نوشته شده توسط:(19 آبان ۱۳۹۱ ۱۱:۴۱ ق.ظ)nasi1391 نوشته شده توسط: با قضیه مستر حل میشود. ولی برای یادگیری و تمرین بیا تغییر متغییر بدیمٰ، بجای n بزاریم پنج به توان k در نتیجه :
[tex]T(5^k)=T(5^(k-1)) (log(5^k))^2=T(5^(k-1)) k^2[/tex]
اینجا چطوری [tex]k^{2}[/tex] بدست آوردین؟
[tex](log(5^{k}))^{2}=log^{2}5^{k}=klog^{2}5[/tex]
اولآ که : وقتی چیزی به توان یه چیز دیگه میرسه اول باید اون توان اول رو حساب کرد یعنی : [tex]{{A^3}^{2}}^{5}=((A^3)^{2})^{5}\neq A^{(3^{({2}^{5})})}[/tex]
خیلی تابلو دیگه ! (من فرض کردم پایه لگاریتم ۵ است به همین دلیل لگاریتم از بین رفته)
درسته. داشتم پاک می کردم ولی دیر صفحه ام بالا میاد.
میشه با جایگذاری هم به جواب رسید.
[tex]g(k)=g(k-1) k^{2}=k^{2} (k-1)^{2} ... 1=\sum i^{2}= \frac{k(k 1)(2k 1)}{6}= \frac{logn(logn 1)(2logn 1)}{6}[/tex]
مبنای لگاریتم ۵ هست.
ممنون از همهتون :)
ظاهرا باید روی این پیچیدگی عبارات بازگشتی بیشتر کار کنم.
اگه منبع خوبی برای یادگیری این قسمت دارید، ممنون میشم معرفی کنید.
باز هم ممنون