۰
subtitle
ارسال: #۱
ی سوال از علوم کامپیوتر ۸۶ /یک سوال شبهه ناک در جواب!
باسلام
ببخشید به نظر من میشه گزینه ۴ => ولی خودش میگه گزینه ۲
توجیه من :
طبق یک نکته در قضیه master اگر اختلاف توانی بین سمت چپ و راست نباشه => باید طرف راست. در logضرب بشه
ضمنا log(n!)=nlgn => جواب میشه nlog^2n
ولی... جواب ی چیز دیگه هس!
ببخشید به نظر من میشه گزینه ۴ => ولی خودش میگه گزینه ۲
توجیه من :
طبق یک نکته در قضیه master اگر اختلاف توانی بین سمت چپ و راست نباشه => باید طرف راست. در logضرب بشه
ضمنا log(n!)=nlgn => جواب میشه nlog^2n
ولی... جواب ی چیز دیگه هس!
۰
ارسال: #۲
RE: ی سوال از علوم کامپیوتر ۸۶ /یک سوال شبهه ناک در جواب!
با سلام
طبق قضیه اصلی
[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]n^{\log_{99}100}=n^{1 \epsilon}[/tex]
که [tex]n^{1 \epsilon}>nlog\: n[/tex]
در نتیجه پاسخ [tex]T(n)=\theta(n^{\log_{99}100})[/tex]
ارسال: #۳
RE: ی سوال از علوم کامپیوتر ۸۶ /یک سوال شبهه ناک در جواب!
(۰۷ بهمن ۱۳۹۳ ۰۸:۱۵ ب.ظ)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]
!
ارسال: #۴
RE: ی سوال از علوم کامپیوتر ۸۶ /یک سوال شبهه ناک در جواب!
هرگاه در رابطه بازگشتی [tex]T(n)=aT(\frac{n}{b}) f(n)[/tex]
نسبت [tex]\frac{f(n)}{n^{\log a_b}}\: <\: n^{\epsilon}[/tex]
برقرارباشه . نمیتوان از قضیه مستر استفاده کرد و باید روش استثناشو بکار برد
نسبت [tex]\frac{f(n)}{n^{\log a_b}}\: <\: n^{\epsilon}[/tex]
برقرارباشه . نمیتوان از قضیه مستر استفاده کرد و باید روش استثناشو بکار برد
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close