دوره موضوعی --> حل روابط بازگشتی --> رابطه نهم - نسخهی قابل چاپ |
دوره موضوعی --> حل روابط بازگشتی --> رابطه نهم - - 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]سوالم خیلی ابتداییه اما متوجهش نمیشم ک چطوری [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^\frac{m}{2}})[/tex] تبدیل به [tex]s({\frac{m}{2}})[/tex] میشه میدونم ک باید [tex]2^{m}[/tex] رو با m عوض کنم اما نمیدونم چطوری تبدیل به [tex]({\frac{m}{2}})[/tex] میشه اگه سوالام پیش پا افتاده است معذرت |
RE: دوره موضوعی --> حل روابط بازگشتی --> رابطه نهم - vojoudi - 13 مهر ۱۳۹۲ ۰۳:۲۵ ب.ظ
(۱۳ مهر ۱۳۹۲ ۰۲:۲۹ ب.ظ)atenaa نوشته شده توسط:سلام(10 بهمن ۱۳۹۰ ۰۴:۵۲ ب.ظ)Aurora نوشته شده توسط: .. بنده خدا دوباره تغییر تابع داده ولی کاش تو تغییر تابع دومی اسم تابع رو s نمیگذاشت ! میذاشت p مثلا یعنی این تغییر تابع : [tex]s(2^m)=p(m)[/tex] |