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

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

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

نوع فایل :  .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]

درج مي كنيم . يك رابطه بازگشتي براي زمان اجراي اين نسخه بازگشتي از مرتب سازي درجي بنويسيد .

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