قطعه کد زیر رو در نظر بگیرید. لطفا بگید به نظر شما رابطه بازگشتی برای این قطعه کد چیه؟ و پیچیدگی زمانیش از چه مرتبه ایه.
به نظر میاد این قطعه کد از مرتبه O(logn) باشه. من درختش رو رسم کردم در واقع چون هر ۴ فراخوانی مثل همن فقط یه فراخوانی از مرتبه M(n-3) است و بقیه از مرتبه O(1) هست. به نظرتون این تحلیل درسته؟
خیر درست نیست.اگه آرایه داشتیم حرف شما درست بود یکی رو حساب میکردیم و واسه بقیه دیگه نیازی نبود.
اما توی روابط بازگشتی ما از بقیه شاخه ها(سایر فراخوانی ها) خبر نداریم!
اگه واسه اعداد کوچکتر از ۱۰ یه عدد return میکردیم اونوقت T اینجوری میشد:
T(n)=4*T(n-3) ,T(10)=1
که اگه بسط بدین میشه [tex]O(4^{\left\lceil(n-10)/3\right\rceil})[/tex]
اما الان که داره واسه کوچکتر از ۱۰ هم باز بازگشتی کار میکنه و شرط توقفی نداریم هیچ وقت این الگوریتم پایان نمی پذیره!
در ضمن logn واسه وقتی است که n داره بر یه چیزی تقسیم میشه نه منها!
هر موقع - دیدین یاد فیبوناچی بیفتین که نمایی میشه البته وقتی نمایی میشه که bT(n-a داشته باشیم و میشه b^n/a
معادله یچیدگی زمانی این میشه:
T(n)=4(n-3)+4
که با حل آن یک معادله درجه ۳ به دست میاد و ما از حل آن عاجزیم.
ولی با همان حل دست و پا شکسته فکر میکنم بشه O(4^n/3)=time
به نظر من:
طبق نکته:
(۱۳ آذر ۱۳۸۹ ۰۲:۳۴ ب.ظ)afagh1389 نوشته شده توسط: خیر درست نیست.اگه آرایه داشتیم حرف شما درست بود یکی رو حساب میکردیم و واسه بقیه دیگه نیازی نبود.
اما توی روابط بازگشتی ما از بقیه شاخه ها(سایر فراخوانی ها) خبر نداریم!
اگه واسه اعداد کوچکتر از ۱۰ یه عدد return میکردیم اونوقت T اینجوری میشد:
T(n)=4*T(n-3) ,T(10)=1
که اگه بسط بدین میشه [tex]O(4^{\left\lceil(n-10)/3\right\rceil})[/tex]
اما الان که داره واسه کوچکتر از ۱۰ هم باز بازگشتی کار میکنه و شرط توقفی نداریم هیچ وقت این الگوریتم پایان نمی پذیره!
در ضمن logn واسه وقتی است که n داره بر یه چیزی تقسیم میشه نه منها!
هر موقع - دیدین یاد فیبوناچی بیفتین که نمایی میشه البته وقتی نمایی میشه که bT(n-a داشته باشیم و میشه b^n/a
حق با آفاق هست، دوستان عزیز sal-dovomi و Masoud به این نکته تو شرط بازگشت توجه نکردن. توی شرط بازگشت وقتی می گیم: if (n<=10) then return M(30)، باز هم داریم فراخوانی بازگشتی رو انجام می دیم. اگر عددی رو برمیگردوند می شد نظر شما رو در نظر گرفت. اما نمیشه چون باز هم در شرط بازگشت فراخوانی بازگشتی داریم.
حالا سوال اصلی اینجاست، با وجود اینکه این قطعه کد پایان ناپذیره، آیا نمیشه حدی برای پیچیدیگی زمانیش در نظر گرفت؟ اگر میشه این حد چیه؟
(۱۳ آذر ۱۳۸۹ ۱۰:۵۳ ب.ظ)arshad90 نوشته شده توسط: حق با آفاق هست، دوستان عزیز sal-dovomi و Masoud به این نکته تو شرط بازگشت توجه نکردن. توی شرط بازگشت وقتی می گیم: if (n<=10) then return M(30)، باز هم داریم فراخوانی بازگشتی رو انجام می دیم. اگر عددی رو برمیگردوند می شد نظر شما رو در نظر گرفت. اما نمیشه چون باز هم در شرط بازگشت فراخوانی بازگشتی داریم.
حالا سوال اصلی اینجاست، با وجود اینکه این قطعه کد پایان ناپذیره، آیا نمیشه حدی برای پیچیدیگی زمانیش در نظر گرفت؟ اگر میشه این حد چیه؟
با سلام، حرف شما و آفاق درسته اما من حدث می زنم که شاید منظور برگرداندن یه مقداره (شرط مرزی) و نه فرخوانی دوباره تابع برای مقدار ۳۰
حالا بازم اگه دارم اشتباه مکنم لطف کنید، بهم بگین.
امکانش هست که اشتباه تایپی باشه! ولی چیزی که اینجا نوشته با return یه مقدار غیر بازگشتی فرق داره!!!
این الگوریتم پیچیدگیش بینهایت هست چون هیچوقت تموم نمیشه اگه سوال تستی دادن باید بیشترین مرتبه زمانی بین گزینه‌ها رو واسش انتخاب کنید.