مقایسه الگوریتم ها

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

چطور میتوانیم الگوریتم ها را باهم مقایسه کنیم ؟

درواقع ما زمانی میتوانیم دو الگوریتم را باهم مقایسه کنیم که به ازای ورودی یکسان، خروجی یکسان نیز تولید کنند.قبل از اینکه وارد معیار های مقایسه شویم اجازه بدهید با یک مثال ساده شروع کنیم. فرض کنید مسئله از ما خواسته است که جمع اعداد یک تا N را بدست اوریم و نتیجه رابرگردانیم.

الگوریتم های زیر سه راحل مختلف را برای محاسبه اعداد یک تا N به ما ارائه میدهند:
الگوریتم A جمع را به صورت (1+2+3+4+…..+N) محاسبه میکند،
الگوریتم B جمع را به صورت (0)+(1+1)+(1+1+1)+….+(1+1+…+1) محاسبه میکند.
الگوریتم C جمع را با استفاده از فرمول جبری معروف(n(n+1)/2) محاسبه میکند و جواب را برمیگرداند.

Algorithm A

int n=10000;
int sum=0;
for(int i=1;i<=n;i++){
        sum=sum+i;
}
print(sum);

Algorithm B

int n=10000;
int sum=0;
for(int i=1;i<=n;i++){
       for(int j=1;j<=i;j++){
                     sum=sum+1;
}
} 
print(sum);

Algorithm C

int n=10000;
int sum=n*(n+1)/2;
print(sum);

نتیجه مقایسه سه الگوریتم با جواب یکسان

اگر شما این سه کد را اجرا کنید به جواب درست  50,005,000 خواهید رسید.حالا مقدار N را تغیر بدهید به صد هزار (100,000) و دوباره کد ها را اجرا کنید. دوباره هر سه کد مقدار درست 5،000،050،000 را نمایش خواهند هر چند ممکن است الگوریتم B  با مقداری تاخیر این کار انجام دهد.حال اگر سه الگوریتم را با مقدار یک ملیون امتحان کنید هرچند به جواب درست خواهید رسید اما این بار باید خیلی بیشتر از انچه انتظارش را دارید برای جواب الگوریتم B صبر کنید.

رفع مشکل کندی برنامه و الگوریتم

حال فرض کنید که برای یک مسئله فقط الگوریتمی مانند B را در اختیار داشتیم آنوقت باید چه کار میکردیم؟ از کامپیوتر سریع تری استفاده میکردیم؟ هر چند این هم میتواند یک راه حل باشد اما منطقی تر آن است که الگوریتممان را تغیر بدهیم.

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

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

معیارهای اصلی اندازه گیری کارایی الگوریتم

دو معیار اصلی برای اندازه گیری کارایی الگوریتم ها وجود دارد که به ان ها پیچیدیگی زمانی(time complexity)  و پیچیدیگی فضایی(space complexity) گفته میشود. از این رو حال میتوان گفت بهترین الگوریتم، الگوریتمی است که هم سریع باشد و هم فضای کمتری اشغال کند. هرچند به دلیل ارزان بودن حافظه پیچیدگی فضایی از اهمیت کمی برخوردار است بخاطر همین ما فقط در این مقاله به پیچیدگی زمانی خواهیم پرداخت. به فرایند اندازه گیری پیچیدگی الگوریتم, تحلیل الگورتیم (Algorithm analysis) گفته میشود.

نماد گذاری ها(Notations)

سه نوع نماد گذاری وجود دارد که مفهوم بهترین حالت،حالت متوسط و بدترین حالت را به ما میرسانند. نماد او بزرگ  (Big O) که به معنای بدترین حالت یک الگوریتم است، نماد امگای بزرگ (Big Ω)که به معنای بهترین حالت یک الگوریتم و نماد تتا(Ɵ) که به معنای حالت متوسط یک الگوریتم است. ما بیشتردر تحلیل الگوریتم ها با او بزرگ کارداریم زیرا دیگر خیالمان راحت است که رشد الگوریتممان بالاتر از آن نمی رود.

برای درک بهتر این سه نماد، الگوریتم جست و جوی خطی(linear search) را در نظر بگیرید.

اومگا – Ω

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

او – O

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

تتا – Ɵ

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

اگه همه ی این حالت ها را باهم جمع بزنیم به عبارت (1+2+3+4+….+N) میرسیم که این همان جمع اعداد یک تا N است و برابر با  است که اگر ان را تقسیم بر تعداد کل حالت ها کنیم (تقسیم بر N)عبارت  بدست میاید و چون میتوانیم از ضرایب، اعداد ثابت وعبارت های کم ارزش صرف نظر کنیم (در ادامه توضیح خواهیم داد)میگوییم حالت متوسط این الگوریتم  Ɵ(N) است.

Linearsearch algorithm

int linearsearch(int array[],int key){
for(int i=0;i<array.length,i++){
if(array[i]==key){
return i;
}
}
return -1;
}

اما در قسمت قبلی چرا از ضرایب،اعداد ثابت و عبارت های کم ارزش صرف نظر کردیم؟

این یک دلیل خیلی ساده دارد . فرض کنید بدترین حالت دو الگوریتم بترتیب N و 2N است.میگوییم هر دو الگوریتم از نوع O(N) هستند زیرا اگربرای مثال کامپیوترمان را دو برابر سریع تر کنیم(دستکاری سخت افزار آن) میتوانیم از الگوریتم دوم به الگوریتم اول برسیم. ولی اگر بدترین حالت دو الگوریتم بترتیب N و 2^N باشد همانطور که در شکل زیر میبینید به هیچ وجه نمیتوان از الگوریتم دوم به الگوریتم اول رسید.

نمودار N و 2N

نمودار N و  2^N

نحوه اندازه گیری پیچیدگی زمانی الگوریتم های A,B,C

انتساب ها و عملیات های ساده ریاضی همگی از نوع O(1) هستند،حلقه هایی که شمارنده انها با یک عدد ثابت جمع میشود از نوع O(N) هستند و اگر حلقه تودرتو باشد از نوع O(N²) میشود،اگر حلقه شمارنده ان در عددی ثابت ضرب شود ان حلقه ها معمولا از نوع O(Logn) میباشند.با این حساب میتوان گفت الگوریتم A ،B ، C که جمع اعداد یک تا N را محاسبه میکردند بترتیب(N+3)،(N²+3)، (5) میباشند که با حذف ضرایب ثابت پیچیدگی زمانی انها بترتیب از نوع,O(N) O(1),O(N²) میباشد.

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

منابع:کتاب Data structure and abstraction with java