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

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

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

 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)) ادغام شوند .