(۰۴ اسفند ۱۳۹۵ ۰۱:۰۸ ب.ظ)alimamala نوشته شده توسط:  با عرض سلام
دوستا من مسدله ی زیر رو از طریق قضیه ی اصلی می رم و جواب رو گزینه ی ۲ بدست می آرم، ولی مدرسان می گه گزینه ی ۱ درسته. چرا ؟

دوست عزیز من فکر می کنم شما درست حل کردید ، من هم از روش جایگذاری حل کردم به گزینه ی ۲ رسیدم ، مدرسان چه راه حلی و چه استدلالی ارائه داده؟

(۰۴ اسفند ۱۳۹۵ ۰۱:۳۴ ب.ظ)hasanmousavi نوشته شده توسط:  

(04 اسفند ۱۳۹۵ ۰۱:۰۸ ب.ظ)alimamala نوشته شده توسط:  با عرض سلام
دوستا من مسدله ی زیر رو از طریق قضیه ی اصلی می رم و جواب رو گزینه ی ۲ بدست می آرم، ولی مدرسان می گه گزینه ی ۱ درسته. چرا ؟

دوست عزیز من فکر می کنم شما درست حل کردید ، من هم از روش جایگذاری حل کردم به گزینه ی ۲ رسیدم ، مدرسان چه راه حلی و چه استدلالی ارائه داده؟

متاسفانه مثل خیلی از سوالات، درست و کامل توضیح نداده، این راه حلش هست:

(۰۴ اسفند ۱۳۹۵ ۰۱:۰۸ ب.ظ)alimamala نوشته شده توسط:  با عرض سلام
دوستا من مسدله ی زیر رو از طریق قضیه ی اصلی می رم و جواب رو گزینه ی ۲ بدست می آرم، ولی مدرسان می گه گزینه ی ۱ درسته. چرا ؟

نکته این تست اینکه باید بین کد بازگشتی و رابطه زمان اجرای ان یعنی $T(n)$ تفاوت قائل بشیم .باید ببینیم که تابع بازگشتی کد با چه مقداری هر بار فراخوانی میشه(که اینجا با نصف ورودی قبلیش) و هزینه اجرای هر بار فراخوانی چقدر است که در اینجا یه تست if داریم با هزینه $O(1)$ ,و یه عمل جمع داریم با هزینه $O(1)$ یعنی $T(n)=T(\frac{n}{2})+O(1)$
که مرتبش لگاریتمیه. دوباره میگم اینجا رابطه بازگشتی زمان اجرا داده نشده بلکه یک کد بازگشتی داده شده که باید رابطه بازگشتی زمان اجرای ان را بدست اوریم