لطفا به نکات زیر در هنگام خرید دانلود پاورپوینت آناليز الگوريتم ها توجه فرمایید.

1-در این مطلب، متن اسلاید های اولیه دانلود پاورپوینت آناليز الگوريتم ها قرار داده شده است 2-به علت اینکه امکان درج تصاویر استفاده شده در پاورپوینت وجود ندارد،در صورتی که مایل به دریافت  تصاویری از ان قبل از خرید هستید، می توانید با پشتیبانی تماس حاصل فرمایید 3-پس از پرداخت هزینه ، حداکثر طی 12 ساعت پاورپوینت خرید شده ، به ادرس ایمیل شما ارسال خواهد شد 4-در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل اسلاید ها میباشد ودر فایل اصلی این پاورپوینت،به هیچ وجه بهم ریختگی وجود ندارد 5-در صورتی که اسلاید ها داری جدول و یا عکس باشند در متون زیر قرار نخواهند گرفت

اسلاید ۱ :

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

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

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

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

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

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

اسلاید ۲ :

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

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

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

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

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

اسلاید ۳ :

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

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

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

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

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

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

اسلاید ۴ :

تعريف نماد :

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

اسلاید ۵ :

كران بالا(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) است.

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

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

اسلاید ۶ :

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

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

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

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

به عبارت ديگر

اسلاید ۷ :

حد محصور(Ө) :

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

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

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

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

اسلاید ۸ :

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

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

ü

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

اسلاید ۹ :

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

۱) f(n)=

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

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

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

اسلاید ۱۰ :

توجه

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

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 (

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