سلام دوستان
من دو تا فرمول رو با مثال توضیح میدم
میبینیم که به یک تناقضی میرسیم
لطفا راهنمایی کنید و نظر خودتون رو بگید
برای محاسبه مرتبه زمانی روابط بازگشتی توی جزوه دکتر جوادی دیدم که نوشته
چنانچه رابطه بازگشتی به شکل زیر باشد که در آن
m مقدار ثابت
و
g(n)
تابع چند جمله ای باشد، آنگاه خواهیم داشت
T(n)=T(n-m) + g(n)
هزینه اجرایی برابر:
T(n)=O(n*g(n))
مثال:
T(n)=T(n-1)+1
T(n)=O(n*1)=O(n)
حال فرمول دوم:
اگر رابطه به صورت زیر باشد و همه مقادیر ثابت باشند
T(n)=k*T(n-m)+c
هزینه اجرایی برابر
T(n)=تتا(k^(n/m))
مثال :
T(n)= 2 T(n-1) +1
هزینه اجرایی
teta(2^n)
حال سوال اینجاست که
اگه مثال اولی که نوشتم رو با حالت دومی حل کنیم( همه شرایط دوم رو داره) هزینه اجرایی مثال اول میشه
teta ( 1^n)
----------------------------
خب چرا با دو روش دو تا جواب مختلف بدست آوردیم؟؟؟
ممنون میشم جواب بدین [/align]
در فرمول دوم یک شرط روی K داریم
اگر K=1 آنگاه مرتبه زمانی (n) خواهد شد.
بسیار ممنونم