پاورپوینت با موضوع تحليل الگوريتم ها (مسائل و تمرين ها)

لینک دانلود و خرید پایین توضیحات

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

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

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

قسمتی از متن .ppt :

تحليل الگوريتم ها (مسائل و تمرين ها)

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

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


فهرست مطالب و اسلایدها:

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

درستي قانون Horner

وارونگي

رشد توابع

نمادهاي استاندارد و توابع عمومي

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

نكات مهم درسي

پيچيدگي زماني برخي توابع عمومي