جواب این سوال چی میشه ؟
t (n)=3t(n/3+5)+n/2
جواب با قضیه master میشه nlogn
مشکل من اینجاست که +۵ داخل پرانتز رو چی کار کنین. در نظر نگیریم؟
در اینجا می تونیم از اون ۵ چشم پوشی کنیم.
(۲۶ دى ۱۳۹۰ ۰۷:۰۳ ب.ظ)yaali نوشته شده توسط: در اینجا می تونیم از اون ۵ چشم پوشی کنیم.همینطوره، بعدش از حالت ۲ قضیه مستر استفاده میکنیم.
(۲۶ دى ۱۳۹۰ ۰۸:۴۰ ب.ظ)Masoud05 نوشته شده توسط:چرا از ۵ چشم پوشی می کنیم؟(26 دى ۱۳۹۰ ۰۷:۰۳ ب.ظ)yaali نوشته شده توسط: در اینجا می تونیم از اون ۵ چشم پوشی کنیم.همینطوره، بعدش از حالت ۲ قضیه مستر استفاده میکنیم.
(۲۶ دى ۱۳۹۰ ۰۹:۵۰ ب.ظ)saeedeh123 نوشته شده توسط:(26 دى ۱۳۹۰ ۰۸:۴۰ ب.ظ)Masoud05 نوشته شده توسط:چرا از ۵ چشم پوشی می کنیم؟(26 دى ۱۳۹۰ ۰۷:۰۳ ب.ظ)yaali نوشته شده توسط: در اینجا می تونیم از اون ۵ چشم پوشی کنیم.همینطوره، بعدش از حالت ۲ قضیه مستر استفاده میکنیم.
در CLRS گفته اگر مقادیر داخل جزء صحیح بودند می تونیم از موارد جزئی صرف نظر کنیم و با توجه به اینکه ۵ هم در مقابل این رابطه جزئی است می تونیم ازش صرف نظر کنیم
اگه بجای ۵ نوشته بود، ۱۰۰۰ اونوقت چشم پوشی نمی شد؟
یعنی اونوقت باید از روش درخت حل می شد؟
(۱۷ شهریور ۱۳۹۱ ۱۰:۵۹ ب.ظ)azad_ahmadi نوشته شده توسط: اگه بجای ۵ نوشته بود، ۱۰۰۰ اونوقت چشم پوشی نمی شد؟
یعنی اونوقت باید از روش درخت حل می شد؟
فرق زیادی نمی‌کنه.
در مقابل nهای بالا الگوریتم باید تحلیل بشه. میشه اینطور گفت٬ اگر نمودار رفتار الگوریتم رو داشته باشیم٬ این نمودار در nهای خیلی بزرگ٬ تقریباً حالت یکنواخت پیدا می‌کنه. مگر توابع خاص مثل مثلثاتی و...
همانطور که دوستمان هم گفتند٬ اگر داخل جزء صحیح باشه٬ قابل چشم‌پوشی هست. مثلاً اگر به جای ۵ نوشته می‌شد n در اینصورت٬ شرایط فرق می‌کرد.
خیلی ممنون. جواب خوبی بود.