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

1395/1/18 --- 5858

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

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

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

در این جلسه همون مباحث رو ادامه میدیم و چند نکته درباره ی پیچیدگی زمانی یک الگوریتم بیان میکنیم و انشاءالله در آخر مقدمات روش تقسیم و حل رو با شروع میکنیم

.خب نماد θ رو تعریف میکنیم..

نماد θ دقیقا مرتبه ی یک الگوریتم رو تعیین میکنه .. درواقع θ بیانگر حد متوسط زمان اجرای یک الگوریتم هست یعنی زمان اجرای یک الگوریتم در حالت میانگین .

پس ( θ(g(n) شامل توابعی هست که رشدشون تقریبا مساوی و یکسان با gn  باشه .

اما دوتا نماد دیگر هم داریم که ω و o  هستند . ω شکل اکید و o هم شکل اکید O هست .

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

فرض کنید که ما دو تابع  f و g داریم و میخوایم بدونیم رشد کدوم بیشتره و یا میخوایم بدونیم از چه نمادی باید استفاده کنیم برای این دو تابع . اگه بخوایم از حد استفاده کنیم کافیه عبارت زیر رو حساب کنیم :

 

lim fx/gx

که x  به سمت بی نهایت میل خواهد کرد . ( f و g توابعی بر حسب متغیر x هستند )

پس داریم حد در بی نهایت رو محاسبه میکنیم . اما برای جواب این حد ، 3 حالت پیش میاد :

1-جواب بی نهایت خواهد بود .

2-جواب 0 خواهد بود.

3-جواب یک عدد ثابت غیر از صفر خواهد بود .

اگه جواب بی نهایت بشه ، یعنی سرعت رشد تابع f بسیار بیشتر از تابع  g هست . اگه جواب صفر بشه ، یعنی سرعت رشد تابع f بسیار کمتر از تابع  g هست چون اگر متغیر رو به سمت بی نهایت ببریم ، مقدار صورت کسر نسبت به مخرج کسر بسیار کوچک تر میشه .البته هردوی اونها دارن زیاد میشن ولی سرعت رشد صورت خیلی کمتر از مخرجه که در این صورت کسر به سمت صفر میل خواهد کرد . اگر هم جواب یک عدد ثابت مثل c بشه که c مخالف صفر باشه ، به این معنی خواهد بود که توابع f و g دارای سرعت رشد تقریبا یکسان هستند .

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

اگر عبارتی که محاسبه کردیم ( حد نسبت تابع f به g ) مبهم شد ، میتونیم از راه هایی مثل قاعده ی هوپیتال استفاده کنیم تا جواب حد ، یکی از حالت های ذکر شده بیاد .

 

اما الان میخوایم یک قضیه ای رو بگیم به نام "قضیه ی اصلی" که بسیار در محاسبه ی پیچیدگی زمانی الگوریتم ها کاربرد داره . شکل خلاصه ی این قضیه به این صورت هست :

پیچیدگی زمانی

البته دقت کنید که در حالت دوم (case 2) ،  منظور  log n بر مبنای b هست .

 

فرض کنید مثلا شکل پیچیدگی زمانی یک الگوریتم به فرم بالا باشه

طبق قضیه ی اصلی واضح هست که مرتبه ی زمانی چنین الگوریتمی  θ(n^2 هست .

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

 

اما اجازه بدید بریم سراغ روش تقسیم و حل :

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

از جمله مهمترین الگوریتم هایی که در این روش قرار میگیرن عبارت هستن از :

1-جست و جوی دودویی

2-مرتب سازی ادغامی

3-مرتب سازی سریع

4-الگوریتم استراسن

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

 

مهمترین جاهایی که الگوریتم های موجود در روش تقسیم و حل در اونها جواب نمیده عبارت هستن از :

1- زمانی که نمونه ای با اندازه ی n به دو یا چند نمونه تقسیم بشه که اندازه ی اونها هم تقریبا n باشه .

در این حالت معمولا پیچیدگی زمانی الگوریتم به صورت نمایی خواهد بود که اصلا جالب نیست !!

2- زمانی که نمونه ای با اندازه ی n تقریبا به n نمونه ی با اندازه ی n/k تقسیم بشه که k یک عدد ثابت هست .

در این جا هم پیچیدگی زمانی الگوریتم به صورت n^log n خواهد بود .

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

در جلسه ی بعد هم انشاءالله دو یا سه الگوریتم بیان شده در روش تقسیم و حل رو با ذکر پیچیدگی زمانی اونها توضیح میدیم و مقدمات بحث " برنامه ریزی پویا " رو بیان خواهیم نمود .

تا دیدار بعدی شما رو به خدای بزرگ می سپارم . موفق و پیروز و سالم و تندرست باشید .

کلمات کلیدی