اینم توضیح بدید لطفاً
[tex]T(n)=T(\frac{n}{3}) T(\frac{n}{6}) n^{\sqrt{\log n}}[/tex]
با فرض [tex]T(n)=1[/tex] برای مقادیر کوچک n
(۱۸ دى ۱۳۹۳ ۰۳:۵۱ ب.ظ)Ametrine نوشته شده توسط: اینم توضیح بدید لطفاً
[tex]T(n)=T(\frac{n}{3}) T(\frac{n}{6}) n^{\sqrt{\log n}}[/tex]
با فرض [tex]T(n)=1[/tex] برای مقادیر کوچک n
سلام
برای حل این رابطه بازگشتی میتونیم به صورت تقریبی با محاسبه کران بالا و پایین رابطه پیچیدگی اون رو حساب کنیم.
خوب اول کران بالا رو حساب میکنیم که برای محاسبه اون رابطه به صورت زیر میشه:
[tex]T(n)=2T(\frac{n}{3}) n^{\sqrt{\log n}}[/tex]
که میتونیم با استفاده از قضیه اصلی حلش کنیم و پیچیدگیش برابر [tex]Theta(n^{\sqrt{\log n}})[/tex]
حالا کران پایین رو به دست میاریم که رابطه به صورت : [tex]T(n)=2T(\frac{n}{6}) n^{\sqrt{\log n}}[/tex] میشه و باز هم با استفاده از قضیه اصلی پیچیدگیش برابر [tex]\theta(n^{\sqrt{\log n}})[/tex] هست.
پس در کل پیچیدگیش برابر [tex]\theta(n^{\sqrt{\log n}})[/tex] میشه و گزینه دوم درسته.
حل با کران بندی رابطه.
[tex]t(n)<=2t(\frac{n}{3}) n^{\sqrt{\log n}}\in\theta(n^{\sqrt{\log n}})[/tex]
از طرفی
[tex]t(n)>=2t(\frac{n}{6}) n^{\sqrt{\log n}}\in\theta(n^{\sqrt{\log n}})[/tex]
پس
[tex]t(n)\in\theta(n^{\sqrt{\log n}})[/tex]
(۱۸ دى ۱۳۹۳ ۰۵:۳۳ ب.ظ)shayesteb نوشته شده توسط:(18 دى ۱۳۹۳ ۰۳:۵۱ ب.ظ)Ametrine نوشته شده توسط: اینم توضیح بدید لطفاً
[tex]T(n)=T(\frac{n}{3}) T(\frac{n}{6}) n^{\sqrt{\log n}}[/tex]
با فرض [tex]T(n)=1[/tex] برای مقادیر کوچک n
سلام
برای حل این رابطه بازگشتی میتونیم به صورت تقریبی با محاسبه کران بالا و پایین رابطه پیچیدگی اون رو حساب کنیم.
خوب اول کران بالا رو حساب میکنیم که برای محاسبه اون رابطه به صورت زیر میشه:
[tex]T(n)=2T(\frac{n}{3}) n^{\sqrt{\log n}}[/tex]
که میتونیم با استفاده از قضیه اصلی حلش کنیم و پیچیدگیش برابر [tex]Theta(n^{\sqrt{\log n}})[/tex]
حالا کران پایین رو به دست میاریم که رابطه به صورت : [tex]T(n)=2T(\frac{n}{6}) n^{\sqrt{\log n}}[/tex] میشه و باز هم با استفاده از قضیه اصلی پیچیدگیش برابر [tex]\theta(n^{\sqrt{\log n}})[/tex] هست.
پس در کل پیچیدگیش برابر [tex]\theta(n^{\sqrt{\log n}})[/tex] میشه و گزینه دوم درسته.
ممنون چه ساده گفتید
مرسییییی، باحال بود!
خواهش میکنم
در این مواقع میشه از این قاعده که تو کتاب مرجع هم نوشته شده استفاده کرد
[tex]T(n)=T(\alpha n)\: T(\beta n)\: f(n)[/tex]
به طوری که هرگاه
[tex]\alpha\: \beta\: <\: ۱[/tex]
بود پاسخ میشه
[tex]O(f(n))[/tex]
[tex]\alpha\: \beta\: =۱[/tex]
[tex]\: O(n\: \log\: n)[/tex]
و اگر بزرگتر از یک بود مجموع تعداد اعناصر هر سطر را به اندازه بزرگتریت ارتفاع جمع میکنیم