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

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

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

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

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

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

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

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