۰
subtitle
ارسال: #۱
پیچیدگی زمانی یک قطعه کد نسبتا جالب!
قطعه کد زیر رو در نظر بگیرید. لطفا بگید به نظر شما رابطه بازگشتی برای این قطعه کد چیه؟ و پیچیدگی زمانیش از چه مرتبه ایه.
به نظر میاد این قطعه کد از مرتبه O(logn) باشه. من درختش رو رسم کردم در واقع چون هر ۴ فراخوانی مثل همن فقط یه فراخوانی از مرتبه M(n-3) است و بقیه از مرتبه O(1) هست. به نظرتون این تحلیل درسته؟
به نظر میاد این قطعه کد از مرتبه 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
اما توی روابط بازگشتی ما از بقیه شاخه ها(سایر فراخوانی ها) خبر نداریم!
اگه واسه اعداد کوچکتر از ۱۰ یه عدد 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
ارسال: #۳
RE: پیچیدگی زمانی یک قطعه کد نسبتا جالب!
(۱۳ آذر ۱۳۸۹ ۰۲:۳۴ ب.ظ)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)، باز هم داریم فراخوانی بازگشتی رو انجام می دیم. اگر عددی رو برمیگردوند می شد نظر شما رو در نظر گرفت. اما نمیشه چون باز هم در شرط بازگشت فراخوانی بازگشتی داریم.
حالا سوال اصلی اینجاست، با وجود اینکه این قطعه کد پایان ناپذیره، آیا نمیشه حدی برای پیچیدیگی زمانیش در نظر گرفت؟ اگر میشه این حد چیه؟
۰
ارسال: #۴
پیچیدگی زمانی یک قطعه کد نسبتا جالب!
معادله یچیدگی زمانی این میشه:
T(n)=4(n-3)+4
که با حل آن یک معادله درجه ۳ به دست میاد و ما از حل آن عاجزیم.
ولی با همان حل دست و پا شکسته فکر میکنم بشه O(4^n/3)=time
T(n)=4(n-3)+4
که با حل آن یک معادله درجه ۳ به دست میاد و ما از حل آن عاجزیم.
ولی با همان حل دست و پا شکسته فکر میکنم بشه O(4^n/3)=time
۰
۰
ارسال: #۶
پیچیدگی زمانی یک قطعه کد نسبتا جالب!
امکانش هست که اشتباه تایپی باشه! ولی چیزی که اینجا نوشته با return یه مقدار غیر بازگشتی فرق داره!!!
۰
ارسال: #۷
پیچیدگی زمانی یک قطعه کد نسبتا جالب!
این الگوریتم پیچیدگیش بینهایت هست چون هیچوقت تموم نمیشه اگه سوال تستی دادن باید بیشترین مرتبه زمانی بین گزینه‌ها رو واسش انتخاب کنید.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close