باسلام
ببخشید به نظر من میشه گزینه ۴ => ولی خودش میگه گزینه ۲
توجیه من :
طبق یک نکته در قضیه master اگر اختلاف توانی بین سمت چپ و راست نباشه => باید طرف راست. در logضرب بشه
ضمنا log(n!)=nlgn => جواب میشه nlog^2n
ولی... جواب ی چیز دیگه هس!
[attachment=17896]
با سلام
طبق قضیه اصلی
[tex]n^{\log_{99}100}=n^{1 \epsilon}[/tex]
که [tex]n^{1 \epsilon}>nlog\: n[/tex]
در نتیجه پاسخ [tex]T(n)=\theta(n^{\log_{99}100})[/tex]
(۰۷ بهمن ۱۳۹۳ ۰۸:۱۵ ب.ظ)maryam.roshan نوشته شده توسط: با سلامببخشید قضیه master ی استثنا داشت که میگفت باید اختلاف مرتبه ای از n باشه=> ولی این نیس! log هس
طبق قضیه اصلی
[tex]n^{\log_{99}100}=n^{1 \epsilon}[/tex]
که [tex]n^{1 \epsilon}>nlog\: n[/tex]
در نتیجه پاسخ [tex]T(n)=\theta(n^{\log_{99}100})[/tex]
مثل سوال [tex]4T(\frac{n}{2}) n^2\log n[/tex]
!
هرگاه در رابطه بازگشتی [tex]T(n)=aT(\frac{n}{b}) f(n)[/tex]
نسبت [tex]\frac{f(n)}{n^{\log a_b}}\: <\: n^{\epsilon}[/tex]
برقرارباشه . نمیتوان از قضیه مستر استفاده کرد و باید روش استثناشو بکار برد