سلام دوستان کسی میدونه حاصل سیگمای زیر چی میشه؟؟
![[تصویر: 199917_1.png]](https://img.manesht.ir/199917_1.png)
سیگمای بالا با استفاده از جایگذاری در معادله بازگشتی زیر برای بدست آوردن پیچیدگی محاسباتیش بدست اومده . چطور میشه حلش کرد؟؟:
(T(n) = T(n-1) + (n^4)*(log n
T(3) = 1
ببخشید میشه بگید این سیگما رو از کجا بدست آوردین ؟ منظورم اینه که اصل سوال همینه یا یه مسئله بوده که وسطش نیاز به حل این سیگما شدین ؟
شاید حل خود مسئله آسون تر از این سیگما باشه.
اصل سوال محاسبه پیچیدگی محاسباتی تابع بازگشتی زیره که به با روش جایگزاری به همچین سیگمای میرسه
(T(n) = T(n-1) + (n^4)*(log n
T(3) = 1
[tex]O(n^5logn)[/tex]
ممنون بابت جوابتون. ببخشید میشه راه حل تشریحیشو بنویسید اصلا نمیدونم چطور این جواب به دست اومده
ممنون بابت جوابتون. ببخشید میشه راه حل تشریحیشو بنویسید اصلا نمیدونم چطور این جواب به دست اومده
سلام مجدد
داریم : [tex]T(n)=T(n-1) n^4logn[/tex] با تغییر متغیر [tex]n=2^k[/tex] داریم : [tex]T(2^k)=T(2^k-1) k2^{4k}[/tex]
با کمی دستکاری و تعمیم این رابطه بدست میاریم :
[tex]T(2^k)-T(2^k-1)=k2^{4k}[/tex]
[tex]T(2^k-1)-T(2^k-2)=log(2^k-1)2^{4log(2^k-1)}\approx log(2^k)2^{4log(2^k)}=k2^{4k}[/tex]
[tex]T(2^k-2)-T(2^k-3)=log(2^k-2)2^{4log(2^k-2)}\approx log(2^k)2^{4log(2^k)}=k2^{4k}[/tex]
[tex]T(2^k-3)-T(2^k-4)=log(2^k-3)2^{4log(2^k-3)}\approx log(2^k)2^{4log(2^k)}=k2^{4k}[/tex]
[tex]\vdots[/tex]
[tex]T(4)-T(3)=log(4)2^{4log4}=512[/tex]
تعداد این سطر ها [tex]2^k[/tex] است در نتیجه با جمع این سطر ها داریم :
[tex]T(n)=2^k * [k2^{4k}] T(3) \approx nlog(n)2^{4logn}=nlog(n)16^{logn}=n^5logn[/tex]
ممنون از جوابتون اما چرا؟؟؟
![[تصویر: 200017_Capture.png]](https://img.manesht.ir/200017_Capture.png)
تقریب زدم ! میدونم که یکی نیست !
![[تصویر: 200088_Capture11.png]](https://img.manesht.ir/200088_Capture11.png)
نه درست نیست
چرا؟
چون :
[tex]T(n)=\sum_{i=0}^{\frac{n}{4}}(n-i)^4log(n-i) 1[/tex]
حق با شماست اشتباه تایپی بود تصیح شد.
![[تصویر: 200125_Capture20.png]](https://img.manesht.ir/200125_Capture20.png)