تالار گفتمان مانشت
دوره موضوعی --> حل روابط بازگشتی --> رابطه نهم - نسخه‌ی قابل چاپ

دوره موضوعی --> حل روابط بازگشتی --> رابطه نهم - - rasool - - 10 بهمن ۱۳۹۰ ۱۲:۵۰ ب.ظ

هوالعلیم

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

RE: دوره موضوعی --> حل روابط بازگشتی --> رابطه نهم - Aurora - 10 بهمن ۱۳۹۰ ۰۴:۵۲ ب.ظ

جواب:[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]

RE: دوره موضوعی --> حل روابط بازگشتی --> رابطه نهم - atenaa - 13 مهر ۱۳۹۲ ۱۲:۰۲ ب.ظ

(۱۰ بهمن ۱۳۹۰ ۰۴:۵۲ ب.ظ)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]
میشه

RE: دوره موضوعی --> حل روابط بازگشتی --> رابطه نهم - SnowBlind - 13 مهر ۱۳۹۲ ۰۱:۲۰ ب.ظ

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

RE: دوره موضوعی --> حل روابط بازگشتی --> رابطه نهم - atenaa - 13 مهر ۱۳۹۲ ۰۲:۲۹ ب.ظ

(۱۰ بهمن ۱۳۹۰ ۰۴:۵۲ ب.ظ)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] میشه
اگه سوالام پیش پا افتاده است معذرتUndecided

RE: دوره موضوعی --> حل روابط بازگشتی --> رابطه نهم - vojoudi - 13 مهر ۱۳۹۲ ۰۳:۲۵ ب.ظ

(۱۳ مهر ۱۳۹۲ ۰۲:۲۹ ب.ظ)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] میشه
اگه سوالام پیش پا افتاده است معذرتUndecided
سلام
بنده خدا دوباره تغییر تابع داده ولی کاش تو تغییر تابع دومی اسم تابع رو s نمیگذاشت ! میذاشت p مثلا
یعنی این تغییر تابع : [tex]s(2^m)=p(m)[/tex]