پاورپوینتی در مورد تحلیل الگوریتم و مسایل و تمرینات مرتبط

اختصاصی از ژیکو پاورپوینتی در مورد تحلیل الگوریتم و مسایل و تمرینات مرتبط دانلود با لینک مستقیم و پر سرعت .

بسم الله الرحمن الرحیم - فرمت فایل : Powerpoint - تعداد اسلایدها : 15 اسلاید -

تحلیل الگوریتم ها

 1 . با استفاده ازاستقرای ریاضی نشان دهید زمانی که n توان صحیحی از 2 است جواب رابطه بازگشتی زیربرابرچیست ؟

                               اگر n = 2                                      2

                               اگربرای k>1 ، n = 2      T(n) =    2T(n/2) + n 

2 . مرتب سازی درجی می تواند به صورت یک روال بازگشتی بشرح زیر بیان شود . به منظور مرتب کردن A[1..n] ، آرایه A[1...n-1] را بطور بازگشتی مرتب کرده و سپس A(n) را درآرایه مرتب شده A[1..n-1] درج می کنیم . یک رابطه بازگشتی برای زمان اجرای این نسخه بازگشتی از مرتب سازی درجی بنویسید .مرتب سازی درجی روی آرایه های کوچک در مرتب سازی ادغام

1 . یک تغییر در مرتب سازی ادغام را در نظر بگیرید که درآن n/k زیر لیست با طول k با استفاده از مرتب سازی درجی ، مرتب شده و سپس با استفاده از فرایند ادغام استاندارد ادغام می شوند و k مقداری است که باید مشخص شود .

 a . نشان دهید که n/k زیر لیست هر یک با طول k می توانند بوسیله مرتب سازی درجی در بدترین حالت در زمان Θ(n/k)  مرتب شوند.

 b . نشان دهید که زیر لیست ها می توانند دربدترین حالت درزمان Θ(nlg(n/k)) ادغام شوند .