پاورپوینت حل روابط بازگشتی (pptx) 32 اسلاید

دسته بندی : پاورپوینت

نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )

تعداد اسلاید: 32 اسلاید

قسمتی از متن PowerPoint (.pptx) :

فصل سوم حل روابط بازگشتی هدف: بررسی روش هایی برای محاسبه پیچیدگی زمانی الگوریتم های بازگشتی بدترین زمان اجرای مرتب سازی ادغامی به منظور سادگی کران پایین و بالا را یکسان فرض می کنیم. T(n)= 2 T)  (n/2) (+ n T(n)= ө(1) if n=1 T)  (n/2) (+T) (n/2 )(+ ө(n) if n>1 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=1 برقرار است بنابراین به ازای n>=0 T(n) є O(nlog n) مثال 3-1 حدس: برای عدد ثابت عددی مانند a T(n)<= anlogn برای n=1 درست کار نمی کند T(n)= c1 if n=1 2 T) n/2(+c2n if n>1 حدس دوباره : برای عدد ثابت عددی مانند a T(n)<= anlogn+b پایه استقرا: برای n=1 و عبارت b>=c1 برقرار است : T(n)<= anlogn+b T(n)= c1 if n=1 2 T) n/2(+c2n if n>1 فرض استقرا: T(k)<= aklogk+b حکم استقرا: T(n)<= anlogn+b به ازای :n>=2 T(n)<= 2 T)n/2(+c2n به ازای k=n/2 : T(n)<= 2(a (n/2) log (n/2) +b )+c2n <= 2 a (n/2) (log n – log 2) +2b +c2n <= an log n – an + 2b + c2n <= an log n + b در صورتی که a>= c2+b باشد رابطه بالا برقرار است. بنابراین ثابت کردیم که : T(n) <= an log n + b به شرطی که b>=c1 و a>= c2+b به ازای مقادیر خاصی می توان رابطه بالا را ساده تر کرد . a=c1+c2 T(n)<=(c1+c2)log n + c1 به عبارت دیگر T(n)Є O(n log n) روش تکرار با جایگذاری با استفاده از جایگذاری های متوالی جواب مناسب تولید می گردد. مثال : T(n)= 2T(n/2)+d D یک ثابت زمانی است.