(۱۰ دى ۱۳۹۳ ۱۲:۱۴ ب.ظ)miladcr7 نوشته شده توسط:  سلام رابطه اصلی که اینه:
[tex]T(n)=2\sqrt{n}T(\sqrt{n}) nLog(n)[/tex]

خب من میام طرفین رو بر [tex]n[/tex] تقسیم میکنم .حالا داریم:
[tex]\frac{T(n)}{n}=\frac{2\sqrt{n}T(\sqrt{n})}{n} \frac{nLog(n)}{n}\rightarrow\frac{​T(n)}{n}=\frac{2T(\sqrt{n})}{\sqrt{n}} Log(n)[/tex]

حالا من این کارو انجام میدم: [tex]\frac{T(n)}{n}=F(n)[/tex] (دقت کن اینجا کار خاصی انجام ندادیم فقط یه تغییر اسم سادس)
پس رابطمون حالا به شکل زیر میشه:
[tex]F(n)=2F(\sqrt{n}) Log(n)[/tex]

خب حالا تغییر متغیر رو انجام میدیم([tex]n=2^m\rightarrow m=Logn[/tex] )
پس داریم:
[tex]F(2^m)=2F(\sqrt{2^m}) m\rightarrow F(2^m)=2F(2^{\frac{m}{2}}) m[/tex]

یه تغییر اسم دیگه هم میدیم:
[tex]a(m)=2a(\frac{m}{2}) m[/tex]

که طبق قضیه اصلی زمان اجرا میشه:[tex]mLog(m)[/tex] و از طرفی میدونیم که [tex]m=Log(n)[/tex] و با جایگذاری داریم:
[tex]Log(n).LogLog(n)[/tex]

پس حالا این نتیجه کار شد:

[tex]\frac{T(n)}{n}=Log(n).LogLog(n)\rightarrow T(n)=n.Log(n).LogLog(n)[/tex]

فک کنم باید جواب گزینه ۳ شه