سلام.
$T(n)=2T(\frac{n}{2})+\frac{n}{\log n}$
روش درخت بازگشت:
هزینه ی سطح اول(ریشه) : $\frac{n}{\log n}$
هزینه ی سطح دوم : $\frac{\frac{2n}{2}}{\log(\frac{n}{2})}=\frac{n}{\log n-\log2}=\frac{n}{\log n-1}$
هزینه ی سطح سوم: $\frac{\frac{4n}{4}}{\log(\frac{n}{4})}=\frac{n}{\log n-\log4}=\frac{n}{\log n-2}$
هزینه ی سطح چهارم: $\frac{\frac{8n}{8}}{\log(\frac{n}{8})}=\frac{n}{\log n-\log8}=\frac{n}{\log n-3}$
.
.
هزینه ی سطح k ام: $\frac{n}{\log n-(k-1)}$
.
.
هزینه ی سطح logn-۱ ام: $\frac{n}{\log n-(\log n-1)}=\frac{n}{1}$
مجموع این هزینه ها: $\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$

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

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

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


پاسخ:


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