پاورپوینت حل روابط بازگشتی
نوع فایل:
پاورپوینت
قابل
ویرایش 32 اسلاید
T(n)= 2 T) ën/2û(+ n
هر بار
تعداد اعداد نصف می شود. بنابراین بعد از logn مرتبه به انتها می رسیم
چون زیر
مسئله ها را با O(n)
با هم ترکیب می کنیم.
بنابراین
حدس می زینم پیچیدگی :
T(n)= n log n
T(n)=
n log n
پایه
استقرا:
n=
2 T(2)<=c 2 log 22
C>=
T(2)/2 >0
فرض
استقرا(k<n):
T(k)<=CK
log k2
باید
ثابت کنیم:
T(n)<=c
n log n2
برچسب ها:
پاورپوینت حل روابط بازگشتی حل روابط بازگشتی روابط بازگشتی بازگشتی پاورپوینت حل روابط