با عرض سلام
دوستا من مسدله ی زیر رو از طریق قضیه ی اصلی می رم و جواب رو گزینه ی ۲ بدست می آرم، ولی مدرسان می گه گزینه ی ۱ درسته. چرا ؟
(۰۴ اسفند ۱۳۹۵ ۰۱:۰۸ ب.ظ)alimamala نوشته شده توسط: با عرض سلامدوست عزیز من فکر می کنم شما درست حل کردید ، من هم از روش جایگذاری حل کردم به گزینه ی ۲ رسیدم ، مدرسان چه راه حلی و چه استدلالی ارائه داده؟
دوستا من مسدله ی زیر رو از طریق قضیه ی اصلی می رم و جواب رو گزینه ی ۲ بدست می آرم، ولی مدرسان می گه گزینه ی ۱ درسته. چرا ؟
(۰۴ اسفند ۱۳۹۵ ۰۱:۳۴ ب.ظ)hasanmousavi نوشته شده توسط:(04 اسفند ۱۳۹۵ ۰۱:۰۸ ب.ظ)alimamala نوشته شده توسط: با عرض سلامدوست عزیز من فکر می کنم شما درست حل کردید ، من هم از روش جایگذاری حل کردم به گزینه ی ۲ رسیدم ، مدرسان چه راه حلی و چه استدلالی ارائه داده؟
دوستا من مسدله ی زیر رو از طریق قضیه ی اصلی می رم و جواب رو گزینه ی ۲ بدست می آرم، ولی مدرسان می گه گزینه ی ۱ درسته. چرا ؟
متاسفانه مثل خیلی از سوالات، درست و کامل توضیح نداده، این راه حلش هست:
(۰۴ اسفند ۱۳۹۵ ۰۲:۳۲ ب.ظ)signal_micro نوشته شده توسط:داداش فکر می کنم اشتباه می کنی اولا مستر جواب میده ، ثانیا با روشهای دیگه هم که حل میشه جواب گزینه ۲ هست(04 اسفند ۱۳۹۵ ۰۱:۰۸ ب.ظ)alimamala نوشته شده توسط: با عرض سلاماز جواب مدرسان سر در نیوردم ولی شما تو قضیه اصلی اشتباه کردی f(n) از مرتبه [tex]n^c[/tex] نیست از مرتبه o(1) هست([tex]n^0[/tex]) پس از مورد دوم قضیه اصلی بری(نه اولی سومی) [tex]f(n)=n^0\times\log^n[/tex] میشه پس گزینه۱ هست مشابه این مثال تو کتاب ساختمان داده ابراهیمی بود( منو بگو هنوز الگوریتم رو شروع نکردم بیچاره میشم آخرش
دوستا من مسدله ی زیر رو از طریق قضیه ی اصلی می رم و جواب رو گزینه ی ۲ بدست می آرم، ولی مدرسان می گه گزینه ی ۱ درسته. چرا ؟)
سلام. وقت بخیر.
جواب کتاب درسته. سوال مقدار نهایی رو نخواسته، دفعات تکرار رو خواسته. مقدار نهایی از مرتب [tex]\theta(n)[/tex] میشه. ولی پیچیدگی محاسباتیش (دفعاتی که دستورها اجرا میشن) همون چیزیه که تو جواب کتاب هست.
(۰۴ اسفند ۱۳۹۵ ۰۱:۰۸ ب.ظ)alimamala نوشته شده توسط: با عرض سلام
دوستا من مسدله ی زیر رو از طریق قضیه ی اصلی می رم و جواب رو گزینه ی ۲ بدست می آرم، ولی مدرسان می گه گزینه ی ۱ درسته. چرا ؟
نکته این تست اینکه باید بین کد بازگشتی و رابطه زمان اجرای ان یعنی [tex]T(n)[/tex] تفاوت قائل بشیم .باید ببینیم که تابع بازگشتی کد با چه مقداری هر بار فراخوانی میشه(که اینجا با نصف ورودی قبلیش) و هزینه اجرای هر بار فراخوانی چقدر است که در اینجا یه تست if داریم با هزینه [tex]O(1)[/tex] ,و یه عمل جمع داریم با هزینه [tex]O(1)[/tex] یعنی [tex]T(n)=T(\frac{n}{2})+O(1)[/tex]
که مرتبش لگاریتمیه. دوباره میگم اینجا رابطه بازگشتی زمان اجرا داده نشده بلکه یک کد بازگشتی داده شده که باید رابطه بازگشتی زمان اجرای ان را بدست اوریم