آموزش طراحی و تحلیل الگوریتم قسمت دوم

1395/1/12 --- 10601

به نام خداوند بخشنده و مهربان

سلام عرض می کنم خدمت همه ی شما عزیزان ..

من سعید ضیادید هستم و در خدمت شما هستم با جلسه ی دوم آموزش طراحی و تحلیل الگوریتم ها .

اجازه بدید یک خلاصه از مباحث جلسه ی قبل رو خدمت شما عرض کنم . در جلسه ی گذشته با یکسری از تعاریف اولیه ی مرتبط با الگوریتم و فلوچارت آشنا شدیم و همچنین ویژگی های الگوریتم رو بیان کردیم . کمی هم درباره ی کارآمدی الگوریتم مطالبی ارائه کردیم .

اما در این جلسه به طور کلی میخوایم درباره ی کارآمدی الگوریتم صحبت کنیم . همونطور که گفته شد ، ملاک و معیار کارایی یک الگوریتم ، پیچیدگی زمانی و پیچیدگی فضاست . ما دراین سری از آموزش ها بیشتر درباره ی پیچیدگی زمانی صحبت میکنیم .

اما اجازه بدید کمی راجع به پیچیدگی فضا صحبت کنیم تا بعد مفصل بریم سراغ پیچیدگی زمانی

شبه کد زیر رو در نظر بگیرید :

float OP1(float a , float b , float c){
return a+b+c*a/a+c+2.0 ;
}

این برنامه یک عبارت خاصی رو محاسبه میکنه و نتیجه رو برمیگردونه. فضای مورد نیاز برای یک چنین برنامه ای شامل دو بخش ثابت و متغیر است . بخش ثابت ، مستقل از بعضی ویژگی های ورودی و خروجی هست و شامل فضای دستور العمل ، فضای لازم برای ذخیره ی کد برنامه ، فضای لازم برای متغیر های ساختاری با اندازه ی ثابت و ثابت ها و غیره هست . بخش متغیر هم شامل فضای لازم برای متغیر های ساختاری و تغییر پذیر برنامه هست که وابسته به نمونه ی موجود در مسئله هستن . همچنین این بخش شامل فضای لازم برای متغیر های مرجع و پشته ی بازگشتی هم هست .

فضای لازم برای هر برنامه ای مثل P رو اگر S(P) فرض کنیم ، میشه به صورت S(P)=c+sp نوشت که توی اون c یک مقدار ثابت هست و sp مشخصات نمونه ی مسئله هست .

برای برنامه ای که بالا گفتیم ، نمونه ی مسئله با حروفی نشون داده شدن (a,b,c). با این فرض که همه ی این مقادیر در یک کلمه از حافظه ذخیره بشن متوجه میشیم فضای مورد نیاز برای تابع درون مسئله ، مستقل از ویژگی های نمونه هست . پس sp برابر صفر هست .

اما بریم سراغ پیچیدگی زمانی .

پیچیدگی زمانی یعنی مقدار زمانی که یک کامپیوتر برای اجرای کامل یک برنامه لازم داره . هر برنامه یکسری مراحلی داره و از دستوراتی تشکیل شده . معمولا برای تشخیص زمان اجرای برنامه هم به مراحل اجرای برنامه توجه می کنند . اما یک مرحله از برنامه رو میشه به عنوان یک قسمت بامعنی از نظر دستوری تعریف کرد که زمان اجرای اون به ویژگی های نمونه بستگی نداره . تعداد مراحلی که به هر کدوم از دستورات برنامه باید نسبت داده بشه ، به ماهیت اون دستور بستگی داره .

حالا برای آشنایی بیشتر میایم تعداد مراحل لازم برای اجرای برخی از دستورات موجود در یک زبان استاندارد ، مثلا ++C ، رو بررسی میکنیم . البته تعداد مراحل ذکر شده برای برخی دستورات به صورت تقریبی هستن و ممکنه توی برنامه های مختلف تغییر کنن ولی اغلب اوقات به همین شکل هستن .

تمامی توضیحات در این زبان دارای صفر مرحله هست . یعنی برای توضیحات هیچ مرحله ای درنظر گرفته نمیشه . دستور های تعریفی و اعلان هم مرحله ای ندارن ( دارای صفر مرحله هستن .) منظور از دستور های تعریفی ، دستوراتی هستند که متغیر ها، ثابت ها ، توابع یا نوع دسترسی رو مشخص میکنن

هر عبارت دارای 1 مرحله هست . ( به جز عبارات فراخوانی توابع )

تعداد مراحل عمل انتساب <a>=> برابر با تعداد مراحل <b> هست . که a شامل یک متغیر و b شامل یک عبارت هست . البته اگه aتابعی از ویژگی های نمونه باشه ، اونوقت تعداد مراحل انتساب برابر با مجموع اندازه ی متغیر و تعداد مراحل عبارت هست .

دستور شرطی if else هم 1 مرحله داره .

حلقه ی for(a;b;c) هم دارای b+c مرحله هست . (منظور از b و c ، تعداد مراحل اونهاست . )

فراخوانی توابع و دستورات مدیریت حافظه دارای 1 مرحله هستن .

شبه کد زیر رو در نظر بگیرید :

float sum1(float *a , const int n)
1. { 
2.  float s=0 ; 
3. for ( int i=0;i<n;i++)
4. s=s+a[i];
5.  return s;
6.  }

این شبه کد ، مجموع عناصر درون یک آرایه ی n عضوی رو برمیگردونه.

خط اول این برنامه ، مرحله ای نداره

خط دوم دارای 1 مرحله هست

خط سوم که یک حلقه ی تکرار هست ، دارای n+1 مرحله هست .

خط چهارم هم n مرحله داره . (اگرچه عمل انتساب هست ولی n بار داره تکرار میشه . )

خط پنجم دارای 1 مرحله هست .

خط ششم هم مرحله ای نداره .

پس میشه گفت تعداد کل مراحل شبه کد بالا برابر با 2n+3 هست .

یک سوال :

فرض کنیم که تعداد مراحل برنامه ی A برابر 2n+3 و تعداد مراحل برنامه ی B برابر 2n+2 باشد. آیا از این

مطلب میشه نتیجه گرفت که برنامه ی A از B کندتر انجام میشه؟

جواب منفیه !!

نمیشه نتیجه ی مشخصی گرفت .. چون مراحل دارای واحد زمانی معینی نیستن . ممکنه 3 مرحله ی موجود برنامه ی A به طور مجموع سریع تر از 2 مرحله ی B باشن .

پس میشه نتیجه گرفت اون اعداد ثابت ملاک خوبی نیستن پس در پیچیدگی زمانی اونها رو میتونیم درنظر نگیریم و به طور کلی بگیم پیچیدگی زمانی به n وابسته هست . به همین دلیل اصطلاحا میگیم هردو برنامه ی A و B از مرتبه ی n هستن .

همونطور که میدونیم ، ممکنه الگوریتم های مختلفی برای حل یک مسئله وجود داشته باشن . مثلا برای مرتب سازی یک سری داده ، الگوریتم هایی نظیر : Bubble sort-Selection sort و .....وجود دارن . برای تشخیص دامنه ی کارآمدی الگوریتم ها ، به معیار هایی نظیر پیچیدگی زمانی و پیچیدگی فضای حافظه نیاز داریم. بنابراین منظور

ما از تجزیه و تحلیل الگوریتم ها ، مشخص کردن زمان اجرای برنامه ها هست . هر پردازنده در هرلحظه بیش از یک دستور رو نمیتونه اجرا کنه و این مستقل از نوع پردازنده و سیستم هست. پس هر برنامه در کامپیوتر ها باید دستور به دستور انجام بشه و بنابراین تعداد دستورات برنامه ، مدت زمان اجرای برنامه را نشون میدن . هدف از

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

معمولا زمان اجرای یک برنامه رو با Tn نشون میدن .

اما یکی از نماد های مهم نماد اوی بزرگ هست .

تعریف big O: حد بالای زمان اجرای برنامه هست . به معنای دیگر ، زمان اجرای یک برنامه در بدترین حالت . فرض کنیم fn زمان اجرای برنامه بر حسب n باشه. میگیم الگوریتم دارای زمان اجرای Ogn هست اگه c>0 وجود داشته باشه به طوریکه

fn<=cgn

وقتی میگیم On^2 یعنی تمام توابعی که رشدشون کمتر یا مساوی تابع n^2 هست . و وقتی پیچیدگی زمانی یک الگوریتم On^2 باشه یعنی در بدترین حالت ممکن ، تابع پیچیدگی زمانیش از n^2 بیشتر نمیشه ..پس پیچیدگی رو برحسب یک تابع بیان میکنیم .

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

O(log n) < O(n) < O(nlog n) < O(n2) < O(n3) < O(n!)

پس مثلا الگوریتمی که مرتبه ی زمانیش در بدترین حالت ممکن برابر با log n باشه ، بسیار از لحاظ زمانی بهتر از الگوریتمی با زمان اجرای n^3 خواهد بود .

تعریف Ω

حد پایین زمان اجرای یک برنامه هست . یعنی زمان اجرای یک برنامه در بهترین حالت. میگیم الگوریتم دارای زمان اجرای Ωgn هست اگه

fn≥Ωgn

پس Ωgn شامل توابعی هست که رشدشون بزرگتر یا مساوی gn باشه. الگوریتمی با چنین مرتبه ای هم در بهترین حالت دارای پیچیدگی زمانی gn میشه

 

خب دوستان عزیزم برای این جلسه کافیه

در جلسه ی بعد نماد Θ رو تعریف میکنیم . چند مثال برای محاسبه ی پیچیدگی زمانی همراه با نمایش نماد ها بیان میکنیم . کمی درباره ی روابط بازگشتی حرف میزنیم و مقدمات مبحث "تقسیم و حل" رو ارائه میکنیم ..

کلمات کلیدی