دانلود پاورپوینت آنالیز الگوریتم ها

بخشی از پاورپوینت

اسلاید 1 :

سوال هايي كه در اين فصل به آنها پاسخ مي دهيم:

(1چرا آناليز الگوريتم ها انجام مي شود؟                                       

(2معيارهاي ارزيابي الگوريتم چيست؟

(3روش محاسبه چگونه است؟

(4تعريف نماد ها چگونه است؟

(5روش مقايسه چگونه است؟

اسلاید 2 :

چرا آناليز الگوريتم ها انجام مي شود؟                                       
برای دانستن این موضوع که كداميك از الگوريتم ها براي حل مسئله وتبديل به كد مناسب تر است.
هدف آناليز الگوريتم ها
مقايسه بين الگوريتم هاي مختلف براي رسيدن به بهترين الگوريتم

معيارهاي الگوريتم بهينه

.1پیچیدگی زمانی (زمان مورد نياز براي اجراي الگوريتم)

.2پیچیدگی حافظه ای (حافظه مورد نياز براي اجراي الگوريتم)

.3 پیچیدگی طراحی و پیاده سازی

اسلاید 3 :

روش محاسبه چگونه است؟

اين يك سوال پارامتري است كه داراي جواب پارامتري می باشد .

     * انواع پاسخ به حل مسئله : (عددي- معادلاتي- تابعي)

الگوريتمي كه قراراست مسئله اي را حل كند تعدادي داده را از ورودي مي گيرد بنابراين پيچيدگي زماني وابسته به سايز ورودي است.

üسايز ورودي: تعداد داده هاي ورودي كه با n نشان مي دهيم.

üپیچیدگی زمانی به صورت تابعي از n ( سايز ورودي ) مطرح مي شود.

اسلاید 4 :

تعريف نماد :

• كران بالا)  O،( o
• كران پايين) Ω،ω  (
• حد محصور (Ө)

اسلاید 5 :

كران بالا(O):

براي تابع  g(n)، O(g(n)) مجموعه اي از توابع است:

  O(g(n)) = {f(n) : $c, n0 >0 such that "n³ n0 , 0 £f(n) £cg(n)}

به زبان ساده c.g(n) به ازاي nهاي بزرگ، يك حد بالايي براي f(n) است.

توجه :     به عنوان حد آستانه تابع است .

مثال :پس از     تابع     رشد بيشتري نسبت به     دارد.

اسلاید 6 :

كران پايين(ω):

براي تابع  g(n)، w(g(n)) مجموعه اي از توابع است:

w(g(n))={f(n):"c>0 $n0>0 such that "n³n0  0 £cg(n) < f(n)}

به زبان ساده cg(n) به ازاي n هاي بزرگ، يك حد پاييني محض براي f(n) است.

به عبارت ديگر

اسلاید 7 :

حد محصور(Ө) :

براي تابع  g(n)، Ө (g(n)) مجموعه اي از توابع است:

  Ө (g(n))={f(n):$c1,c2,n0>0 s.t. "n³ n0  0£c1g(n) £f(n)£c2g(n)}

üبه زبان ساده g(n) و f(n) نرخ رشد يكساني دارند.

üf(n) از مرتبه Ө (g(n)) است اگر هم O(g(n)) و هم W(g(n))  باشد.

اسلاید 8 :

سوال :آيا تابعي كه به عنوان مصرف زمان مطرح مي شود،تمام مولفه هاي آن مهم است؟ (به عنوان مثال f(n)=3n2+5n-100  )

پاسخ: خير، زيرا زماني كه تعداد داده ها زياد مي شود از مولفه هاي كوچكتر مي توان صرف نظر كرد؛ همچنين الگوريتم براي تعداد داده هاي كم به راحتي جواب مي دهد ولي براي داده هاي زياد دچار مشكل مي شويم.

ü

üدر آناليز الگوريتم جمله اي كه تعيين كننده ي حد تابع زمانيكه n به سمت بينهايت مي رود براي ما مهم است.

اسلاید 9 :

مثال: اگر تابع پیچیدگی زمانی الگوریتمی به صورت زیر باشد درجه رشد تابعرا مشخص کنید .

1) f(n)=

پاسخ: بیشترین درجه رشد زمانی است که عدد ورودی ما فرد باشد در نتیجه  O(n3) وكمترين آن زمانی است عدد زوج باشد پس (n2)  Ωو چون کران بالا و پایین با هم برابر نیست Ө وجود ندارد.

2)f(n)=3n2+5n+10

پاسخ: تابع ما یک ضابطه ای است و کران بالاي O(n2) و كران پایين Ω(n3) دارد كه برابر هم هستند در نتیجه درجه رشد تابع برابر است با Ө (n2).

اسلاید 10 :

توجه

üدرجه رشد توابع به سه دسته عمده لگاریتمی ، چند جمله ای و نمایی تقسیم می شود که رابطه زیر بین آن ها صادق است.

O(1) < O(log n) < O(n) < O(n1.1) < O(n 2) < …                      < O(1.1n)  < O(2 n) < O(3 n)< … < O(n! )<O(n n (

üبه عبارت دیگر درجه رشد   :   نمایی >> چند جمله ای >> لگاریتمی