پاورپوینت حل روابط بازگشتی
نوع فایل:
پاورپوینت
قابل
ویرایش 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)=
T(2)/2 >
فرض
استقرا(k
T(k)<=CK
log k2
باید
ثابت کنیم:
T(n)<=c
n log n2
برچسب ها:
PowerPoint-hal-ravabet-bazgashti