پاورپوینت آناليز الگوريتم ها (pptx) 54 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 54 اسلاید
قسمتی از متن PowerPoint (.pptx) :
آناليز الگوريتم ها
1
الگوريتم : روش حل يك مسئله
گام هاي حل مسئله :
ارايه الگوريتم
اثبات صحت عملكرد
كارايي : 1- شناخت الگوريتم بهينه
2- تبديل به برنامه
شرايط الگوريتم :
ورودي
خروجي
قطعيت
محدوديت
کارايي
2
سوال هايي كه در اين فصل به آنها پاسخ مي دهيم:
چرا آناليز الگوريتم ها انجام مي شود؟
معيارهاي ارزيابي الگوريتم چيست؟
روش محاسبه چگونه است؟
تعريف نماد ها چگونه است؟
روش مقايسه چگونه است؟
3
چرا آناليز الگوريتم ها انجام مي شود؟ برای دانستن این موضوع که كداميك از الگوريتم ها براي حل مسئله وتبديل به كد مناسب تر است. هدف آناليز الگوريتم ها مقايسه بين الگوريتم هاي مختلف براي رسيدن به بهترين الگوريتم
معيارهاي الگوريتم بهينه
پیچیدگی زمانی (زمان مورد نياز براي اجراي الگوريتم)
پیچیدگی حافظه ای (حافظه مورد نياز براي اجراي الگوريتم)
پیچیدگی طراحی و پیاده سازی
4
روش محاسبه چگونه است؟ اين يك سوال پارامتري است كه داراي جواب پارامتري می باشد . * انواع پاسخ به حل مسئله : (عددي- معادلاتي- تابعي)
الگوريتمي كه قراراست مسئله اي را حل كند تعدادي داده را از ورودي مي گيرد بنابراين پيچيدگي زماني وابسته به سايز ورودي است.
سايز ورودي: تعداد داده هاي ورودي كه با n نشان مي دهيم.
پیچیدگی زمانی به صورت تابعي از n ( سايز ورودي ) مطرح مي شود.
5
تعريف نماد :
كران بالا) O،( o
كران پايين) Ω،ω (
حد محصور (Ө)
6
كران بالا(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) است.
توجه : به عنوان حد آستانه تابع است .
مثال :پس از تابع رشد بيشتري نسبت به دارد.
f 2
f 1
f 2 = O (f 1)
n0
n0
n0
f 2
f 1
7
مثال :
T(n) = 2n+2 ≤ 4n → T(n) є O(n)
/* C = 4 ; n0 = 1 */
T(n) = 3n3+2n+1 ≤ 3n3+2n3+n3 = 6n3 → T(n) є O(n3) /* C = 6 ; n0 = 1 */
8
كران بالا(o):
براي تابع g(n)، o(g(n)) مجموعه اي از توابع است:
o(g(n))={f(n) :c>0 n0>0 such that n n0 0 f(n)
