سلام دوستان
جواب این سوال n^2 نمی شه ؟
چون به روش درختی هزینه ی هر سطح n/logn میشه و هزینه ی کل هم همینه . پس جواب میشه n^2.
اشتباه گفتم؟؟
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
سلام.
[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]
سلام :
با تغییر متغیر حل می شود اما من دوس دارم اینو با یه نکته که دقیقا خاطرم نیست از کجا آوردمش حلش کنم.
نکته : اگر توان n در دو طرف یکی شود و توان لگاریتم منفی باشد یعنی :
[tex]f(n)=n^{\log_2^2}=n\: ,\: g(n)=\: nlogn^{-1}[/tex]
آنگاه داریم : [tex]T(n)=\theta(nlog\: log\: n)[/tex]
(۱۶ مهر ۱۳۹۵ ۰۷:۴۵ ب.ظ)wskf نوشته شده توسط: سلام دوستان
جواب این سوال n^2 نمی شه ؟
چون به روش درختی هزینه ی هر سطح n/logn میشه و هزینه ی کل هم همینه . پس جواب میشه n^2.
اشتباه گفتم؟؟
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
سلام.میشه با الگوریتم Akra-bazzi هم این سوال رو حل کرد.که حلش رو خیلی کوتاه و ساده میکنه.
[tex]T(n)=2T(\frac{n}{2})\: +\frac{\: n}{\log n}[/tex]
پاسخ:
[tex]\frac{2}{2^p}\: =\: 1\: \: \: \longrightarrow\: \: \: p\: =1[/tex]
[tex]T(n)\: \epsilon\: \theta(n^p(1+\int_1^n\frac{f(u)}{u^{p+1}}du))[/tex]
[tex]T(n)\: \epsilon\: \theta(n^1(1+\int_1^n\frac{\frac{u}{\log\: u}}{u^2}du))[/tex]
[tex]T(n)\: \epsilon\: \theta(n(1+\int_1^n\frac{1}{u\: \log\: u}du))[/tex]
[tex]T(n)\: \epsilon\: \theta(n(1+\log(\log n)))[/tex]
[tex]T(n)\: \epsilon\: \theta(n\: \log(\log n))[/tex]
[tex]T(n)\: \epsilon\: \theta(n^p(1+\int_1^n\frac{f(u)}{u^{p+1}}du))[/tex]
[tex]T(n)\: \epsilon\: \theta(n^1(1+\int_1^n\frac{\frac{u}{\log\: u}}{u^2}du))[/tex]
[tex]T(n)\: \epsilon\: \theta(n(1+\int_1^n\frac{1}{u\: \log\: u}du))[/tex]
[tex]T(n)\: \epsilon\: \theta(n(1+\log(\log n)))[/tex]
[tex]T(n)\: \epsilon\: \theta(n\: \log(\log n))[/tex]
-------------------------------------------------
توضیح حل انتگرال [tex]\int\frac{1}{u\: \ln\: u}\: du[/tex] :
[tex]x\: =\: \ln\: u[/tex]
[tex]dx\: =\frac{\: 1}{u}\: du[/tex]
[tex]dx\: =\frac{\: 1}{u}\: du[/tex]
[tex]\int\frac{1}{u\: \ln\: u}\: du\: =\: \int\frac{1}{x}\: dx\: =\: \ln\: x\: =\: \ln(\ln\: u)[/tex]