(۱۸ دى ۱۳۹۳ ۰۳:۵۱ ب.ظ)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] میشه و گزینه دوم درسته.

(۱۸ دى ۱۳۹۳ ۰۵:۳۳ ب.ظ)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)<=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]

خواهش میکنم

در این مواقع میشه از این قاعده که تو کتاب مرجع هم نوشته شده استفاده کرد
[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]

و اگر بزرگتر از یک بود مجموع تعداد اعناصر هر سطر را به اندازه بزرگتریت ارتفاع جمع میکنیم