انجمنصفحه اولجستجوی انجمن

[- rasool -]

هوالعلیم

[tex]T(n)=\sqrt{n}T(\sqrt{n}) n[/tex]

[Aurora]

جواب:[tex]n\log \log n[/tex]

ابتدا کل عبارت رو بر n تقسیم می کنیم:

[tex]\frac{t(n)}{n}=\frac{\sqrt{n}t(\sqrt{n})}{n} \frac{n}{n} \Rightarrow \frac{t(n)}{n}= \frac{t(\sqrt{n})}{\sqrt{n}} 1[/tex]
و داریم:
[tex]s(n)=\frac{t(n)}{n}\Rightarrow s(n)=s(\sqrt{n}) 1[/tex]

در اینجا با تغییر متغیر n=2^m داریم:
[tex]s(2^m)=s(\sqrt{2^m}) 1[/tex]
سپس:

[tex]s(2^m)=s({2^\frac{m}{2}}) 1[/tex]
و:

[tex]s(m)=s({\frac{m}{2}}) 1[/tex]

با قضیه masterداریم:

[tex]s(m)\in \theta(log m)[/tex]

با جایگذاری n=2^m یعنی m=log n:

[tex](log m)\Rightarrow log log n[/tex]

و در نهایت کل عبارت را در n ضرب می کنیم چون ابتدا عبارت را بر n تقسیم کرده بودیم:

[tex]n\log \log n[/tex]

[atenaa]

(۱۰ بهمن ۱۳۹۰ ۰۴:۵۲ ب.ظ)Aurora نوشته شده توسط:  جواب:[tex]n\log \log n[/tex]

ابتدا کل عبارت رو بر n تقسیم می کنیم:

[tex]\frac{t(n)}{n}=\frac{\sqrt{n}t(\sqrt{n})}{n} \frac{n}{n} \Rightarrow \frac{t(n)}{n}= \frac{t(\sqrt{n})}{\sqrt{n}} 1[/tex]
و داریم:
[tex]s(n)=\frac{t(n)}{n}\Rightarrow s(n)=s(\sqrt{n}) 1[/tex]

سوالم خیلی ابتداییه اما متوجهش نمیشم ک
چطوری


[tex]\frac{t(\sqrt{n})}{\sqrt{n}}[/tex]
تبدیل به
[tex]s(\sqrt{n})[/tex]
میشه

[SnowBlind]

خب شما توی رابطه [tex]S(n) = \frac{T(n)}{n}[/tex] به جای [tex]n[/tex] قرار بده [tex]\sqrt{n}[/tex]

[atenaa]

(۱۰ بهمن ۱۳۹۰ ۰۴:۵۲ ب.ظ)Aurora نوشته شده توسط:  ..
سپس:

[tex]s(2^m)=s({2^\frac{m}{2}}) 1[/tex]
و:

[tex]s(m)=s({\frac{m}{2}}) 1[/tex]

خیلی ممنون این رو هم میگید ک چطوری
[tex]s({2^\frac{m}{2}})[/tex]
تبدیل به
[tex]s({\frac{m}{2}})[/tex]
میشه
میدونم ک باید [tex]2^{m}[/tex] رو با m عوض کنم
اما نمیدونم چطوری
تبدیل به [tex]({\frac{m}{2}})[/tex] میشه
اگه سوالام پیش پا افتاده است معذرت

[vojoudi]

(۱۳ مهر ۱۳۹۲ ۰۲:۲۹ ب.ظ)atenaa نوشته شده توسط:  

(10 بهمن ۱۳۹۰ ۰۴:۵۲ ب.ظ)Aurora نوشته شده توسط:  ..
سپس:

[tex]s(2^m)=s({2^\frac{m}{2}}) 1[/tex]
و:

[tex]s(m)=s({\frac{m}{2}}) 1[/tex]

خیلی ممنون این رو هم میگید ک چطوری
[tex]s({2^\frac{m}{2}})[/tex]
تبدیل به
[tex]s({\frac{m}{2}})[/tex]
میشه
میدونم ک باید [tex]2^{m}[/tex] رو با m عوض کنم
اما نمیدونم چطوری
تبدیل به [tex]({\frac{m}{2}})[/tex] میشه
اگه سوالام پیش پا افتاده است معذرت

سلام
بنده خدا دوباره تغییر تابع داده ولی کاش تو تغییر تابع دومی اسم تابع رو s نمیگذاشت ! میذاشت p مثلا
یعنی این تغییر تابع : [tex]s(2^m)=p(m)[/tex]