***2
•تحلیل الگوریتم ها
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] درج می کنیم . یک رابطه بازگشتی برای زمان اجرای این نسخه بازگشتی از مرتب سازی درجی بنویسید .
***3
•مرتب سازی درجی روی آرایه های کوچک در مرتب سازی ادغام
یک تغییر در مرتب سازی ادغام را در نظر بگیرید که درآن n/k زیر لیست با طول k با استفاده از مرتب سازی درجی ، مرتب شده و سپس با استفاده از فرایند ادغام استاندارد ادغام می شوند و k مقداری است که باید مشخص شود .
a . نشان دهید که n/k زیر لیست هر یک با طول k می توانند بوسیله مرتب سازی درجی در بدترین حالت در زمان Θ(n/k) مرتب شوند.
b . نشان دهید که زیر لیست ها می توانند دربدترین حالت درزمان Θ(nlg(n/k)) ادغام شوند .
***5
. زمان اجرای مجانبی این قطعه کد برای قانون Horner چیست ؟
b . شبه کدی برای پیاده سازی الگوریتم ارزشیابی ساده چند جمله ای بنویسید که هر جمله از چند جمله ای را از ابتدا محاسبه می کند . زمان اجرای این الگوریتم چیست ؟ در مقایسه با قانون Horner چگونه است ؟
c . ثابت کنید که ثابت زیر یک ثابت حلقه برای حلقه while در خطوط 3- 5 است .
y = ∑ a x