نوع فایل: 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 می توانند بوسیله مرتب سازی درجی در بدترین حالت در زمان Θ(n/k) مرتب شوند. b .
نشان دهید که زیر لیست ها می توانند دربدترین حالت درزمان Θ(nlg(n/k)) ادغام شوند .
درستی قانون Horner قطعه کد زیر قانون horner را برای ارزشیابی چند جمله ای P(x) = ∑ a x = a + x(a + x(a +…+x(a + xa )…)), با ضرایب داده شده a ,a ,…, a و یک مقدار برای x پیاده سازی می کند : 1 y ← 0 2 i ← n 3 While i ≥ 0 4 do y ← a + x .
y 5 i ← i -1 n k =0 k k 0 1 n-1 n i 0 1 n 2 a .
زمان اجرای مجانبی این قطعه کد برای قانون Horner چیست ؟
b .
شبه کدی برای پیاده سازی الگوریتم ارزشیابی ساده چند جمله ای بنویسید که هر جمله از چند جمله ای را از ابتدا محاسبه می کند .
زمان اجرای این الگوریتم چیست ؟
در مقایسه با قانون Horner چگونه است ؟
c .
ثابت کنید که ثابت زیر یک ثابت حلقه برای حلقه while در خطوط 3- 5 است . y = ∑ a x n-(i+1) k =0 k+i+1 k وارونگی 1 .
چه آرایه ای با عناصر مجموعه {1,2,…,n } بیشترین وارونگی ها را دارد ؟
این آرایه چند وارونگی دارد ؟
2 .
چه رابطه ای بین زمان اجرای مرتب سازی درجی و تعداد وارونگی ها درآرایه ورودی وجود دارد ؟
3 .
الگوریتمی ارائه دهید که تعداد وارونگی ها در یک جایگشت روی n عنصر را در بدترین حالت در زمان Θ(nlgn) تعیین کند .
رشد توابع 1 .
فرض کنید f(n) و g(n) بطور مجانبی توابع غیرمنفی باشند .
با استفاده از تعریف اصلی نماد Θ ، ثابت کنید که max(f(n),g(n)) = Θ(f(n) + g(n)) 2 .
توضیح دهید چرا عبارت ” زمان اجرای الگوریتم A حداقل O(n ) است ” ، بی معنی است ؟
3 .
آیا 2 = O(n ) ؟
آیا 2 = O(2 ) ؟
4 .
نشان دهیدهر ثابت حقیقی a وb که b>0 ، ( n+a ) = Θ(n ) n+1 2n 2 2n 2 b b 5 .
متن بالا فقط قسمتی از محتوی متن پاورپوینت میباشد،شما بعد از پرداخت آنلاین ، فایل را فورا دانلود نمایید
لطفا به نکات زیر در هنگام خرید دانلود پاورپوینت: ................... توجه فرمایید !
- در این مطلب، متن اسلاید های اولیه قرار داده شده است.
- به علت اینکه امکان درج تصاویر استفاده شده در پاورپوینت وجود ندارد،در صورتی که مایل به دریافت تصاویری از ان قبل از خرید هستید، می توانید با پشتیبانی تماس حاصل فرمایید
- پس از پرداخت هزینه ،ارسال آنی پاورپوینت خرید شده ، به ادرس ایمیل شما و لینک دانلود فایل برای شما نمایش داده خواهد شد
- در صورت مشاهده بهم ریختگی احتمالی در متون بالا ،دلیل آن کپی کردن این مطالب از داخل اسلاید ها میباشد ودر فایل اصلی این پاورپوینت،به هیچ وجه بهم ریختگی وجود ندارد
- در صورتی که اسلاید ها داری جدول و یا عکس باشند در متون پاورپوینت قرار نخواهند گرفت.
- هدف فروشگاه جهت کمک به سیستم آموزشی برای دانشجویان و دانش آموزان میباشد .
« پرداخت آنلاین »
پاورپوینت تحلیل الگوریتمها