پاورپوینت محاسبه هزینه الگوریتم ها

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

اسلاید 1 :

محاسبه هزینه الگوریتم ها

اسلاید 2 :

تحلیل کارایی
پیچیدگی مکانی space complexity
مقدار فضایی از حافظه که برنامه برای اجرا نیاز خواهد داشت.

پیچیدگی زمانی time complexity
زمانی که طول می کشد برنامه اجرا شود و خروجی را تولید کند.
درس طراحی الگوریتم ها - پیوست دوم - محاسبه هزینه الگوریتم ها- مدرس: بیدکی

اسلاید 3 :

پیچیدگی مکانی
انواع متغیرها
متغیرهای اولیه (int, float, char, …)
متغیرهای غیر اولیه (ترکیبی از متغیرهای اولیه هستند: آرایه، ساختار و .)

معیار فضا: هر متغیر اولیه یک واحد مکانی را اشغال می کند.
درس طراحی الگوریتم ها - پیوست دوم - محاسبه هزینه الگوریتم ها- مدرس: بیدکی

اسلاید 4 :

مثال
محاسبه پیچیدگی مکانی الگوریتم زیر
درس طراحی الگوریتم ها - پیوست دوم - محاسبه هزینه الگوریتم ها- مدرس: بیدکی

اسلاید 5 :

پیچیدگی زمانی [1]
الگوریتم های غیربازگشتی و متوالی
معیار زمان: هر دستورالعمل اجرایی یک واحد زمانی طول می کشد.
مثال:
a = 4
b = a + 3
c = sin(b) * 3.14 / cos (a*2)
Sum ( a , b) {
c = a + b
return c
}
درس طراحی الگوریتم ها - پیوست دوم - محاسبه هزینه الگوریتم ها- مدرس: بیدکی

اسلاید 6 :

الگوریتم های غیر بازگشتی
هزینه حلقه ها
باید تعداد دفعات تکرار دستورات حلقه را محاسبه کرد.
n مرتبه
درس طراحی الگوریتم ها - پیوست دوم - محاسبه هزینه الگوریتم ها- مدرس: بیدکی

اسلاید 7 :

هزینه حلقه for
محاسبه هزینه حلقه for که اندازه گام آن 1 می باشد.
شمارنده حلقه
دستورات بدنه
مرحله آخر حلقه
for i=1 to n {
statement1
…
statementn
}
درس طراحی الگوریتم ها - پیوست دوم - محاسبه هزینه الگوریتم ها- مدرس: بیدکی

اسلاید 8 :

هزینه حلقه for
درس طراحی الگوریتم ها - پیوست دوم - محاسبه هزینه الگوریتم ها- مدرس: بیدکی

اسلاید 9 :

تمرین در کلاس
محاسبه پیچیدگی مکانی و زمانی الگوریتم جمع دو
ماتریس m*n
Sp = ?
Tn = ?
درس طراحی الگوریتم ها - پیوست دوم - محاسبه هزینه الگوریتم ها- مدرس: بیدکی

اسلاید 10 :

پیچیدگی زمانی [2]
الگوریتم های بازگشتی
تعیین رابطه بازگشتی و شرط پایان
رابطه بازگشتی: یک تساوی یا نامساوی است که یک تابع را بر حسب مقدار آن روی ورودیهای کوچکتر توصیف می کند.

پیچیدگی زمانی: از روی متن تابع بدست می آید. رابطه بازگشتی باید بسط داده شود تا به فرم غیر بازگشتی درآید.
روش استقراء
روش جایگزینی
روش استفاده از معادله مشخصه
روش تغییر متغیر
درس طراحی الگوریتم ها - پیوست دوم - محاسبه هزینه الگوریتم ها- مدرس: بیدکی

اسلاید 11 :

مثال
محاسبه فاکتوریل عدد n
محاسبه جمله nام دنباله فیبوناچی
درس طراحی الگوریتم ها - پیوست دوم - محاسبه هزینه الگوریتم ها- مدرس: بیدکی

اسلاید 12 :

روش استقراء
ایجاد یک حدس اولیه برای تابع بازگشتی
هدف: اثبات درستی حدس با استفاده از استقراء

استقراء سه مرحله دارد:
مبنای استقراء: حدس برای شرط اولیه برقرار است
فرض استقراء: فرض می شود که حدس به ازای n صحیح است.
گام استقراء: باید اثبات شود که حدس برای جمله n+1 ام نیز برقرار می باشد.
درس طراحی الگوریتم ها - پیوست دوم - محاسبه هزینه الگوریتم ها- مدرس: بیدکی

اسلاید 13 :

مثال استقراء [1]
T(1) = 1
T(2) = T(1) + 1 = 1+1 = 2
T(4) = T(2) + 1 = 2+1 = 3
T(8) = T(4) + 1 = 3+1 = 4
T(16) = T(8) + 1 = 4+1 = 5
T(n) = lg n +1حدس می زنیم که:
چند جمله را محاسبه می کنیم:
حال باید حدس خود را اثبات کنیم: استقراء
برای n=1:
T(1) = lg 1 + 1 = 1
برای مقادیری از n داریم:
T(n) = lg n +1
چون استقرا برای توانهای دو است:
2p+1 =2n then Tn+1 = T2n
باید نشان دهیم:
T(2n) = lg (2n) + 1
T(n) = T(n/2) + 1 then
T(2n) = T(n) + 1 
T(2n) = lg n + 1 + 1 =lg n + lg 2 + 1 = lg (n*2) + 1 = lg 2n + 1
درس طراحی الگوریتم ها - پیوست دوم - محاسبه هزینه الگوریتم ها- مدرس: بیدکی

اسلاید 14 :

مثال استقراء [2]
T(0) = 1
T(1) = 1*T(0) = 1*1 = 1
T(2) = 2*T(1) = 2*1 = 2
T(3) = 3*T(2) = 3*2 = 6
T(4) = 4*T(3) = 4*6 = 24
T(k) = K*T(k-1) = k!
T(n) = n!حدس می زنیم که:
چند جمله را محاسبه می کنیم:
برای n=0:
T(0) = 0! = 1
برای مقادیری از n داریم:
T(n) = n!
باید نشان دهیم:
T(n+1) = (n+1)!
T(n) = n* T(n-1) then
T(n+1) = (n+1) * T(n) 
T(n+1) = (n + 1)* n! = (n+1) !
حدس خود را با استقراء ثابت می کنیم:
درس طراحی الگوریتم ها - پیوست دوم - محاسبه هزینه الگوریتم ها- مدرس: بیدکی

اسلاید 15 :

روش جایگزینی
T(n) = T(n-1) + 5
T(n-1) = T(n-2) + 5
T(n-2) = T(n-3) +5
…
T(n-k) = T(n-k-1)+5
…
T(1) = 2
T(n) = T(n-1) + 5
= T(n-2) + 5 + 5
= T(n-3) + 5 + 5 + 5
=T(n-4) + 5 + 5 + 5 + 5
…
=T(n-k) + 5k
باید به T(1) برسیم بنابراین:
با جایگذاری مقدار k داریم:
درس طراحی الگوریتم ها - پیوست دوم - محاسبه هزینه الگوریتم ها- مدرس: بیدکی

اسلاید 16 :

تمرین در کلاس
پیچیدگی تابع زیر را بدست آورید:
درس طراحی الگوریتم ها - پیوست دوم - محاسبه هزینه الگوریتم ها- مدرس: بیدکی

اسلاید 17 :

روش استفاده از معادله مشخصه
این روش برای دسته بزرگی از رابطه های بازگشتی خطی، قابل استفاده است.
خطی بودن یعنی اینکه در معادله بازگشتی، هر جمله ti با توان اول خود ظاهر شود مثلاً جملاتی مثل t2i یا tn-itn-j یا tc(n-i) که در آن c یک مقدار ثابت و غیر صفر است (مثل tn/2 و t3(n-4))، مشاهده نمی شود.

حل رابطه های بازگشتی خطی در دو دسته کلی بیان می شود:
بازگشتی خطی همگن
بازگشتی خطی ناهمگن
درس طراحی الگوریتم ها - پیوست دوم - محاسبه هزینه الگوریتم ها- مدرس: بیدکی

اسلاید 18 :

1- حل بازگشتی های خطی همگن
تعریف: بازگشتی زیر را درنظر بگیرید که در آن k و aiها ثابتند:
a0tn+a1tn-1+…+aktn-k = 0
این بازگشتی، معادله خطی همگن با ضرایب ثابت از مرتبه kاُم نام دارد.
یک بازگشتی خطی همگن از مرتبه kاُم، نیازمند k شرط اولیه می باشد.
tn = tn-1 + tn-2
t0 = 0
t1 = 1
دنباله فیبوناچی
درس طراحی الگوریتم ها - پیوست دوم - محاسبه هزینه الگوریتم ها- مدرس: بیدکی

اسلاید 19 :

1- حل بازگشتی های خطی همگن .
معادله مشخصه مربوط به معادله بازگشتی
a0tn+a1tn-1+…+aktn-k = 0
اگر قرار دهیم tn= prn، به صورت زیر خواهد بود:
a0rk+a1rk-1+…+akr0 = 0
اگر بتوانیم k تا ریشه برای معادله مشخصه فوق پیدا کنیم، جوابی به فرم زیر:
an = c1r1n+c2r2n+…+ckrkn
در معادله بازگشتی صدق خواهد کرد و ضرایب ck از شرایط اولیه محاسبه می شوند.
درس طراحی الگوریتم ها - پیوست دوم - محاسبه هزینه الگوریتم ها- مدرس: بیدکی

اسلاید 20 :

مثال (دنباله فیبوناچی)
tn = tn-1 + tn-2
t0 = 0
t1 = 1

معادله مشخصه: r2 - r – 1 = 0 => r1 = (1+√5)/2 , r2 =(1-√5)/2
درس طراحی الگوریتم ها - پیوست دوم - محاسبه هزینه الگوریتم ها- مدرس: بیدکی