10 بهمن 1390, 12:50 ب.ظ
10 بهمن 1390, 04:52 ب.ظ
جواب:[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]
ابتدا کل عبارت رو بر 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]
13 مهر 1392, 12:02 ب.ظ
(10 بهمن 1390 04:52 ب.ظ)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]
میشه
13 مهر 1392, 01:20 ب.ظ
خب شما توی رابطه [tex]S(n) = \frac{T(n)}{n}[/tex] به جای [tex]n[/tex] قرار بده [tex]\sqrt{n}[/tex]
13 مهر 1392, 02:29 ب.ظ
(10 بهمن 1390 04:52 ب.ظ)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] میشه
اگه سوالام پیش پا افتاده است معذرت
13 مهر 1392, 03:25 ب.ظ
(13 مهر 1392 02:29 ب.ظ)atenaa نوشته شده توسط: [ -> ]سلام(10 بهمن 1390 04:52 ب.ظ)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]