تحلیل الگوریتمها
موضوع تحلیل الگوریتمها تعیین میزان منابعی است که برای اجرای هر الگوریتم لازم است. منابعی مثل زمان، حافظه، پهنای باند ارتباطی، یا سختافزار رایانه در نظر گرفته میشوند. اکثر الگوریتمهای طراحی شده برای کار با ورودیهای با طول اختیاری تولید میشوند. کارایی یا پیچیدگی هر الگوریتم را با تابعی نشان میدهند که تعداد مراحل لازم برای اجرای الگوریتم را برحسب طول داده ورودی، یا میزان محلهای گرفته شدهٔ حافظه را بر حسب طول داده ورودی نشان میدهد. پیچیدگی زمانی، مقدارپیچیدگی محاسباتیای را توصیف میکند که در اجرای یک الگوریتم مصرف میشود. غالباً مشاهده میشود که یک مسئله را با استفاده از چندین تکنیک مختلف میتوان حل نمود ولی فقط یکی از آنها به الگوریتمی منجر میشود که از بقیه سریعتر است.
در تجزیه و تحلیل نظری الگوریتم آنچه مشترک است، برآورد پیچیدگی در معنای تقریبی آن است. به عنوان مثال، برآورد تابع پیچیدگی برای ورودی خودسرانه بزرگ. نمادهای
معمولاً تخمینهای تقریبی استفاده میشوند، چرا که پیادهسازیهای مختلف از همان الگوریتم، ممکن است در کارایی متفاوت باشد. با این حال بازده هر دو، با «منطق» پیادهسازی یک الگوریتم داده شده، ضرب در یک ضریب ثابت به نام ثابت مخفی مرتبط است.
در مورد تحلیل الگوریتم باید در مورد موضوعاتی مانند تابع رشد، روش تحلیل الگوریتمهای ترتیبی و بازگشتی، حل رابطههای بازگشتی ساده، همگن و نا همگن و همچنین تحلیل سرشکنی صحبت کرد.
کارایی الگوریتم
در نظریه پیچیدگی محاسباتی، الگوریتمها از حیث کارایی در استفاده از منابعی مانند زمان و فضا (حافظه) مورد بررسی قرار میگیرند. در این بررسی آنچه اهمیت دارد میزان زمان و فضای مورد نیاز برای حل یک مسئلهٔ خاص نیست بلکه چگونگی افزایش میزان زمان و فضای مورد نیاز با بزرگ شدن ورودی الگوریتم مورد توجه است.
مثلاً فرض کنید دو الگوریتم الف و ب برای حل مسئلهٔ زیر پیشنهاد شدهاند. در این مسئله نقشهٔ یک منطقه شامل شهرهای قرار گرفته در آن منطقه، جادههای بین آنها و طول هر جاده و نیز نام دو شهر مبدأ و مقصد داده شدهاست. هدف پیدا کردن کوتاهترین مسیر از مبدأ به مقصد است.
فرض کنید به صورت تجربی مشاهده کردهایم که اگر تنها یک شهر به تعداد شهرهای نقشه اضافه شود الگوریتم الف به دو برابر زمان برای حل مسئله نیاز دارد در حالی که زمان مورد نیاز برای الگوریتم ب وقتی دو برابر میشود که تعداد شهرهای نقشه دو برابر شده باشد. بدیهی است که در چنین شرایطی الگوریتم ب را کاراتر از الگوریتم الف میدانیم.
در نظریه پیچیدگی محاسباتی نیز همین روش را پیمیگیریم ولی به جای روشهای تجربی از روشهای ریاضی استفاده میکنیم. به این منظور ابتدا برای ورودی مسئله یک اندازه تعریف میکنیم. این اندازه میتواند میزان حافظهٔ مورد نیاز برای ذخیره کردن ورودی مسئله باشد. سپس زمان (یا فضای) مورد نیاز برای حل مسئله توسط یک الگوریتم به صورت تابعی از اندازهٔ مسئله محاسبه میشود. به محاسبه یا تقریب زدن این چنین تابعی تحلیل الگوریتم گفته میشود.
در تحلیل الگوریتمها بهترین، بدترین و متوسط زمان اجرا بررسی میشود. هرچند معمولاً بهترین زمان اجرای آن اهمیت ندارد؛ زیرا اساساً بهازای ورودیهای غیر محتمل این حالت رخ میدهد. لیکن لازم است الگوریتمها را در بدترین حالت و در صورت امکان در حالت میانگین تحلیل و بررسی کنیم. ممکن است پیچیدگی الگوریتم در یک حالت میانگین بهتر از پیچیدگیاش دربدترین حالت باشد و این اطلاعات مفیدی در مورد آن الگوریتم است.
الگوریتمها به دو دسته تقسیم میشوند، بازگشتی و ترتیبی. الگوریتمهای ترتیبی را معمولاً با شمارش دفعات اجرای دستوری که بر اساس اندازه دادهٔ ورودی، بیشترین بار اجرا میشود، (در صورتی که زمان اجرای دستور از یک مقدار ثابت تبعیت کند) تحلیل میکنیم. اما زمان اجرا و الگوریتم بازگشتی با رابطههای بازگشتی بیان میشوند. روشهای مختلفی برای حل این نوع رابطهها داریم. یک روش خوب برای حل رابطههای بازگشتی، استفاده از درخت بازگشتی است. این روش نحوه جایگذاری یک عبارت بازگشتی و نیز مقدار ثابتی را که در هر سطح از آن عبارت به دست میآید، نشان میدهد. حاصل جمع مقادیر ثابت تمام سطرها جواب حل بازگشتی است.
برای بررسی خوب بودن یک الگوریتم، باید به آهنگ رشد منحنی زمان اجرا-اندازه ورودی یا میزان حافظه مصرفی-اندازه ورودی توجه کنیم. برای بررسی دقیقتر به بررسی شاخصهای تحلیل الگوریتم و تعریف توابع رشد میپردازیم.
تحلیل زمان اجرای الگوریتم
همانطور که در بالا گفته شد، تحلیل الگوریتم به معنای تخمین میزان منابعی است که الگوریتم به آن نیاز دارد. فرض میکنیم با یک تک پردازندهٔ عمومی پیادهسازی شده با حافظه دسترسی تصادفی (RAM) طرف هستیم و الگوریتم پیادهسازی شدهٔ ما توسط برنامهٔ کامپیوتری، عملیاتها را همزمان انجام نمیدهد. در مدل RAM دستورات تعریف شدهای وجود دارند که اجرا کردنشان از یک مقدار ثابتی تبعیت میکند، دستورهایی که در ساختار کامیپوتر تعبیه شدهاند: مانند عملگرهای حسابی (جمع و تقسیم و ضرب و غیره)، علمیاتهای انتقال اطلاعات (ذخیره کردن، رونویسی کردن حافظه، بازخوانی حافظه و غیره) و عملیاتهای کنترل (فراخوانی توابع، بازگشتناز دستور و غیره).
شبه کد زیر که الگوریتم مرتبسازی حبابی را پیادهسازی میکند در نظربگیرید:
for i=1 to A.length
for j=1 to A.length - i
if A[j]>A[j+1]
swap A[j],A[j+1]
زمان اجرای الگوریتم، جمع زمان اجرای هر دستوری است که اجرا میشود. اگر زمان اجرای هر خط را (که گفتیم مقداری ثابت است) با
برای خط اول:
برای خط دوم:
برای خط سوم:
است.
طبق تعریفی که در قسمت تابع
میزان ثبات محاسباتی
بنا به تعریف، هر الگوریتمی که نوسان رفتاری کمتری از خود نشان دهد، اصطلاحاً از نظر محاسباتی باثباتتر است. نظر به این تعریف، دو موضوع تعیینکنندهٔ میزان ثبات محاسباتی الگوریتم خواهند بود:
- ثبات در مدت زمان اجرا (ثبات زمانی)
- ثبات در کیفیت جواب نهایی
برای سنجش میزان ثبات زمانی، میتوان از شاخص
در این باب چند نکته مدنظر است:
- آزمون نیکویی برازش را میبایست سکس کنید و با سطح اطمینان بالا انجام داد و اساساً با اطمینان زیر ۵۰٪ اساساً معنایی ندارد.
- یک عقیده این است که بهجای بررسی واریانس زمان هر تکرار، واریانس زمان خاتمهٔ الگوریتم را در نظر بگیریم. در این صورت، الگوریتمهای قطعی، دارای ایدهآلترین میزان ثبات زمانی هستند، زیرا همیشه مدت زمان اجرای آنها، روی یک سری از دادههای ورودی معین، یک عدد ثبات است؛ بنابراین، واریانس زمان خاتمهٔ آنها، همواره صفر است.
- اگر یک الگوریتم غیرقطعی را بار بهازای هر یک از شاخصهای اندازهٔواجرا کنیم و میانگین و واریانس زمان خاتمهٔ این الگوریتم غیرقطعی بهازای اندازههایوبهترتیب برابر باوباشه، به شرطی میگوییم این الگوریتم داریا ثبات زمانی است که:
- ضریب تغییرات زمان خاتمه در همهٔ اندازهها، دارای یک کران بالای ثابت متناهی مانند باشد (یعنی) و معمولاًدر نظر میگیرند.
- با افزایش اندازه و ابعاد مسئله، واریانس زمان خاتمهٔ الگوریتم حداکثر به صورت خطی رشد کند. بهعبارت دیگر،
بهطور مشابه، برای سنجش میزان ثبات الگوریتم در کیفیت جواب نهایی میتوان واریانس کیفیت جوابهای الگوریتم را بعد از چند بار اجرا، اندازه گرفت؛ بنابراین، میتوان قواعد نکتهٔ قبل را برای این نوع ثبات هم بیان کرد. واضح است که بهترین عملکرید برای ثبات کیفیت جواب نهایی را الگوریتمهای دقیق دارند.
نرخ همگرایی
مسلماً هر الگوریتمی که سریعتر همگرا شود، مطلوبتر است. این نکته دربارهٔ الگوریتمها دقیق کاملاً صادق است اما دربارهٔ الگوریتمهای تقریبی باید نرخ همگرایی با احتیاط بیشتری بررسی شود. زیرا ممکن است الگوریتم A در مدت زمان کوتاهتری در مقایسه با الگوریتم B به یک نقطهٔ بهینهٔ محلی همگرا شود، اما در عوض الگوریتم B به یک جواب بهینهٔ سراسری همگرا شود. برای بررسی همگرایی که به تنهایی خود یک مقولهٔ جداست به تبیین تعاریف زیر میپردازیم:
الگوریتم همگراشوندهٔ سراسری
اگر الگوریتمی بدینصورت باشد که اگر با هر نقطهٔ آغازین دلخواهی شروع شود و در نهایت به یک جواب مشخص برسد، آن را همگراشوندهٔ سراسری مینامند. از این نوع الگوریتمها میتوان به الگوریتم غیر مرکب (سیمپلکس) اشاره کرد.
مرتبهٔ همگرایی
فرض کنید الگوریتم A با شروع از جواب اولیهٔ
در این صورت مرتبهٔ همگرایی بزرگترین عدد حقیقی نامنفی مانند
که در این حال،
عدهای معتقدند که هرچقدر مرتبهٔ همگرایی الگوریتم بزرگتر باشد، با الگوریتم بهتری سروکار داریم؛ زیرا فاصله از جواب حدی
همگرایی خطی
در توضیح بالا اگر
ثبات نرخ همگرایی
ثبات نرخ همگرایی یکی از شاخصهاییاست که با استفاده از واریانس دادههای ستون شیب همگرایی برای هر الگوریتمی قابل محاسبهاست. هر الگوریتمی که دارای ثبات در مدت زمان اجرا و ثبات در کیفیت جواب نهایی باشد، دارای ثبات در نرخ همگرایی خواهد بود.
هوشمندی الگوریتم
یکی از شاخصهای تحلیل الگوریتمها بحث هوشمندی الگوریتم است. شاید این مقوله تا حد زیاد کیفی به نظر برسد اما بررسی آن خالی از لطف نیست.
این بحث کمی ریشهدار تر از زمانی است که مفهوم الگوریتم و تحلیل آن صورت بندی شد و اساساً این مسئلهٔ اساسی مطرح بود که کمال هوشمندی یک الگوریتم چیست؟ آیا قرابت آن به فکر و استدلال نشانهٔ هوشمندی آن است یا برعکس؛ چون اینطور مینماید که انسانها معمولاً کارها را بهینه انجام نمیدهند. بنا به تعریفی یک الگوریتم را هوشمندانه میگویند اگر:
- هیچگاه و بهازای هیچ نمودی از مسئله خطا نداشته باشد.
- دارای پیچیدگی زمانی و همگرایی بسیار خوبی باشد.
همانطور که محسوس است، این تعریف نیز چندان از ذات کیفی بودن خود شاخص دور نشدهاست. شاید تعریف زیر بتواند قدری به کمٓیسازی این ویژگی کمک کند:
الگوریتم A از الگوریتم B هوشمندتر است اگر بهطور همزمان:
- خطای الگوریتم A کمتر از خطای الگوریتم B باشد.
- پیچیدگی زانی و همگرایی الگوریتم A بدتر از الگوریتم B نباشد.
چند نکته درمورد مقولهٔ هوشمندی مطرح میشود:
- طبق تعریف داده شده میتوان از ترایایی (تعدی) برای بررسی ۳ الگوریتم بهره جست.
- برای یافتن هوشمندی یک الگوریتم (که با توجه به پارامتر «خطا» عموماً برای الگوریتمهای آماری بررسی میشود) میبایست به آزمونهای پیچیدهتری که منجر به سنجش هوشمندی آماری میشود رجوع کرد.
توابع رشد
۱. برای تابع
و میگوییم تابع
۲. برای تابع
ُیعنی آهنگ رشد تابع
۳. برای تابع
ُیعنی آهنگ رشد تابع
نکته: شرط لازم و کافی برای اینکه
قضیه اصلی واکاوی الگوریتمها
در الگوریتمهای بازگشتی که اندازهٔ ورودی n است؛ زمان اجرای الگوریتم از رابطه زیر پیروی میکند:
- که برخاسته از تحلیل درخت بازگشتی الگوریتم است.
متغیر:
Case | حالت بندی روی | توضیحات | توصیف با تابع رشد | مثال |
---|---|---|---|---|
۱ | اگر | آهنگ رشد | جواب به صورت زیر است :
|
اگر |
۲ | وقتی | آهنگ رشد توابع بازگشتی با | جواب به صورت زیر است : | اگر اگر |
۳ | وقتی | آهنگ رشد توابع بازگشتی ایجاد شده زیاد بوده و تعداد برگها به | جواب به صورت زیر است:
| اگر |
تحلیل سرشکنی
گاهی با دنبالهای از اعمال روی دادهساختاری سروکار داریم که هزینهشان بالا ولی تعدادشان پایین است و یا برعکس؛ یا اینکه یک عمل که هزینه زیادی دارد موجب میشود تا همان عمل در مراحل بعد با هزینهٔ کمتری انجام شود. در این حالت هزینهٔ یک عمل در بدترین حالتش زیاد است، اما اگر میانگین مجموع هزینهها را برای همهٔ اعمال موجود در دنباله حساب کنیم؛ هزینهٔ معقولتری نسبت به هزینه در بدترین حالت را به دست آوردهایم؛ که به آن هزینهٔ سرشکنی و به روش محاسبه آن تحلیل سرشکنی میگویند.
روشهای تحلیل سرشکنی
روش انبوهه
در این روش مطابق تعریف، جمع هزینههای اعمال محسابه میشود و بر تعداد آنها تقسیم میشود تا هزینهٔ سرشکن شده بهدست آید.
روش حسابداری
این روش یک مدلسازی با سازوکار خزانهای است. در این روش به ازای هر عمل، مقداری پرداختی وجود دارد. فرض کنید که مبلغی صرف انجام خود عمل میشود و مازاد آن در مخزن ذخیره میشود. در هر عملیات اگر هزینه بیشتر از پرداختی آن نوبت بود از خزانه برای جبران آن استفاده میشود. درصورتی که خزانه هیچگاه کمبود نداشته باشد، میزان پول پرداختی برای هر عمل با هزینهٔ سرشکن شدهٔ آن عمل متناسب است.
روش تابع پتانسیل
این روش تعمیمیافتهٔ همان روش حسابداری است که با فرمولبندی ریاضی بیان و تحلیل میشود.
توضیح تابع پتانسیل
فرض کنید
و آن را هزینهٔ سرشکن شدهٔ عمل
در این صورت داریم:
اگر
یعنی
با نیمنگاهی به روش حسابداری میتوان چنین تناظری میان آن و روش تابع پتانسیل برقرار کرد:
- : مقدار پول موجود در مخزن
- : مقدار پول پرداختی برای عملام
- : مقدار هزینهٔ صرفشده برای عملام
- اگر مابهالتفاوت به مخزن اضافه میشود یعنی:
- اگر برای انجام عملام لازم است به اندازهٔاز مخزن برداریم تا بتوانیم این عمل را انجام دهیم.
- پس موجودی در مخزن خواهد بود:
- برای استفاده از این روش باید تابع پتانسیلی تعریف کنیم که دارای شرایط گفته شده باشد.
مسئلهٔ شمارنده
تحلیل شمارنده با روش انبوهه
یک شمارندهٔ
بیت ۰: با هر افزایش تغییر میکند یعنی در مجموع
بیت ۱: یک در میان تغییر میکند یعنی در مجموع
بیت
تعداد تغییرات بیتها:
پس هزینهٔ سرشکن شدهٔ هر عمل افزایش،
مسئلهٔ پشته
تحلیل پشته با روش تابع پتانسیل
در این روش
اکنون هزینهٔ سرشکن شده را بدست میآوریم:
Push: چون یک عنصر اضافه میشود داریم:
از طرفی چون میدانیم که هزینهٔ درج واقعی
Pop: چون یک عنصر کم میشود داریم:
هزینهٔ واقعی حذف هم
Multi-Pop: چون تعدادی عمل Pop است پس هزینهٔ آن نیز صفر میباشد.
بنابراین چون
هزینهٔ سرشکن شده
روشهای ابتکاری
آنچه که در بالا مطرح شد، شاخصهایی بود برای تحلیل عادی الگوریتمها به کار میرفت؛ لیکن الگوریتمهایی هستند دوگانه (هیبریدی) که حل آنها ابتکاری یا فرا ابتکاری محسوب میشود و رسیدن به آنها از چارچوب یک تحلیل ریاضیاتی ساده و بهکار بردن الگوریتمهای آشنا خارج است که میتوان به نمونههایی از آنها اشاره کرد:
منابع
- قدسی، محمد (۱۳۹۵). دادهساختارها و مبانی الگوریتمها. تهران: انتشارات فاطمی.
- Leiserson، Chales (۲۰۰۹). Introduction to Algortihms.
- عشقی، کورش (۱۳۹۵). تحلیل الگوریتمها و طراحی روشهای فرا ابتکاری. تهران: مؤسسهٔ انتشارات علمی دانشگاه صنعتی شریف.
- ویکیپدیای انگلیسی
پانویس
- ↑ قدسی، دادهساختارها و الگوریتمها، ۶۵
- ↑ قدسی، دادهساختارها و الگوریتمها، ۷۹
- ↑ قدسی، دادهساختارها و الگوریتمها، ۱۰۰
- ↑ قدسی، دادهساختارها و الگوریتمها، ۶۹
- ↑ Introduction to Algortihms, 2.2.
- ↑ "GeeksForGeeks" (به انگلیسی).
- ↑ Introduction to Algortihms, 26-27.
- ↑ عشقی، تحلیل الگوریتمها و طراحی روشهای فرا ابتکاری، ۱۶۵−۱۶۶
- ↑ عشقی، تحلیل الگوریتمها و طراحی روشهای فرا ابتکاری، ۱۶۷−۱۷۲
- ↑ عشقی، تحلیل الگوریتمها و طراحی روشهای فرا ابتکاری، ۱۷۵−۱۷۶
- ↑ قدسی، دادهساختارها و الگوریتمها، ۶۹-۷۱
- ↑ قدسی، دادهساختارها و الگوریتمها، ۷۱-۷۲
- ↑ قدسی، دادهساختارها و الگوریتمها، ۷۲-۷۳
- ↑ Introduction to Algorithm, 94-96
- ↑ قدسی، دادهساختارها و الگوریتمها، ۱۱۶
- ↑ قدسی، دادهساختارها و الگوریتمها، ۱۱۸
- ↑ قدسی، دادهساختارها و الگوریتمها، ۱۲۰−۱۲۱
- ↑ قدسی، دادهساختارها و الگوریتمها، ۱۱۹
- ↑ قدسی، دادهساختارها و الگوریتمها، ۱۲۱−۱۲۳
- ↑ عشقی، تحلیل الگوریتمها و طراحی روشهای فرا ابتکاری، ۲۲۳
- ↑ عشقی، تحلیل الگوریتمها و طراحی روشهای فرا ابتکاری، ۲۵۷
- ↑ عشقی، تحلیل الگوریتمها و طراحی روشهای فرا ابتکاری، ۳۱۹
- ↑ عشقی، تحلیل الگوریتمها و طراحی روشهای فرا ابتکاری، ۳۸۱