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

  دسته بندی : پاورپوینت   نوع فایل:  ppt  _ pptx ( قابلیت ویرایش  )    قسمتی از محتوی متن پاورپوینت :    تعداد اسلاید : 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] درج مي كنيم .يك رابطه بازگشتي براي زمان اجراي اين نسخه بازگشتي از مرتب سازي درجي بنويسيد .k مرتب سازي درجي روي آرايه هاي كوچك در مرتب سازي ادغام 1 .يك تغيير در مرتب سازي ادغام را در نظر بگيريد كه درآن n/k زير ليست با طول k با استفاده از مرتب سازي درجي ، مرتب شده و سپس با استفاده از فرايند ادغام استاندارد ادغام مي شوند و k مقداري است كه بايد مشخص شود . a .نشان دهيد كه n/k زير ليست هر يك با طول k مي توانند …