سلام.
[tex]T(n)=2T(\frac{n}{2})+\frac{n}{\log n}[/tex]
روش درخت بازگشت:
هزینه ی سطح اول(ریشه) : [tex]\frac{n}{\log n}[/tex]
هزینه ی سطح دوم : [tex]\frac{\frac{2n}{2}}{\log(\frac{n}{2})}=\frac{n}{\log n-\log2}=\frac{n}{\log n-1}[/tex]
هزینه ی سطح سوم: [tex]\frac{\frac{4n}{4}}{\log(\frac{n}{4})}=\frac{n}{\log n-\log4}=\frac{n}{\log n-2}[/tex]
هزینه ی سطح چهارم: [tex]\frac{\frac{8n}{8}}{\log(\frac{n}{8})}=\frac{n}{\log n-\log8}=\frac{n}{\log n-3}[/tex]
.
.
هزینه ی سطح k ام: [tex]\frac{n}{\log n-(k-1)}[/tex]
.
.
هزینه ی سطح logn-۱ ام: [tex]\frac{n}{\log n-(\log n-1)}=\frac{n}{1}[/tex]
مجموع این هزینه ها: [tex]\frac{n}{\log n}+\frac{n}{\log n-1}+.....+\frac{n}{\log n-(\log n-2)}+\frac{n}{\log n-(\log n-1)}=n\times(1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{\log n})=n\times\sum_{k=1}^{k=\log n}\frac{1}{k}=n\times\ln k=n\times(\log\log n-\log\log1)=n\times\log\log n[/tex]

(۱۶ مهر ۱۳۹۵ ۰۷:۴۵ ب.ظ)wskf نوشته شده توسط:  سلام دوستان
جواب این سوال n^2 نمی شه ؟
چون به روش درختی هزینه ی هر سطح n/logn میشه و هزینه ی کل هم همینه . پس جواب میشه n^2.
اشتباه گفتم؟؟

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

سلام.میشه با الگوریتم Akra-bazzi هم این سوال رو حل کرد.که حلش رو خیلی کوتاه و ساده میکنه.


پاسخ:


توضیح حل انتگرال [tex]\int\frac{1}{u\: \ln\: u}\: du[/tex] :