تحلیل الگوریتم‌ها
موضوع تحلیل الگوریتم‌ها تعیین میزان منابعی است که برای اجرای هر الگوریتم لازم است. منابعی مثل زمان، حافظه، پهنای باند ارتباطی، یا سخت‌افزار رایانه در نظر گرفته می‌شوند. اکثر الگوریتم‌های طراحی شده برای کار با ورودی‌های با طول اختیاری تولید می‌شوند. کارایی یا پیچیدگی هر الگوریتم را با تابعی نشان می‌دهند که تعداد مراحل لازم برای اجرای الگوریتم را برحسب طول داده ورودی، یا میزان محل‌های گرفته شدهٔ حافظه را بر حسب طول داده ورودی نشان می‌دهد. پیچیدگی زمانی، مقدارپیچیدگی محاسباتی‌ای را توصیف می‌کند که در اجرای یک الگوریتم مصرف می‌شود. غالباً مشاهده می‌شود که یک مسئله را با استفاده از چندین تکنیک مختلف می‌توان حل نمود ولی فقط یکی از آن‌ها به الگوریتمی منجر می‌شود که از بقیه سریعتر است.
در تجزیه و تحلیل نظری الگوریتم آنچه مشترک است، برآورد پیچیدگی در معنای تقریبی آن است. به عنوان مثال، برآورد تابع پیچیدگی برای ورودی خودسرانه بزرگ. نمادهای formula_1 برای این منظور استفاده می‌شوند. مثلاً گفته می‌شود، جستجوی دودویی به اجرا در formula_2 مرحله تناسب دارد.
معمولاً تخمین‌های تقریبی استفاده می‌شوند، چرا که پیاده‌سازی‌های مختلف از همان الگوریتم، ممکن است در کارایی متفاوت باشد. با این حال بازده هر دو، با «منطق» پیاده‌سازی یک الگوریتم داده شده، ضرب در یک ضریب ثابت به نام ثابت مخفی مرتبط است.
در مورد تحلیل الگوریتم باید در مورد موضوعاتی مانند تابع رشد، روش تحلیل الگوریتم‌های ترتیبی و بازگشتی، حل رابطه‌های بازگشتی ساده، همگن و نا همگن و همچنین تحلیل سرشکنی صحبت کرد.
در نظریه پیچیدگی محاسباتی، الگوریتم‌ها از حیث کارایی در استفاده از منابعی مانند زمان و فضا (حافظه) مورد بررسی قرار می‌گیرند. در این بررسی آنچه اهمیت دارد میزان زمان و فضای مورد نیاز برای حل یک مسئلهٔ خاص نیست بلکه چگونگی افزایش میزان زمان و فضای مورد نیاز با بزرگ شدن ورودی الگوریتم مورد توجه است.
مثلاً فرض کنید دو الگوریتم الف و ب برای حل مسئلهٔ زیر پیشنهاد شده‌اند. در این مسئله نقشهٔ یک منطقه شامل شهرهای قرار گرفته در آن منطقه، جاده‌های بین آن‌ها و طول هر جاده و نیز نام دو شهر مبدأ و مقصد داده شده‌است. هدف پیدا کردن کوتاه‌ترین مسیر از مبدأ به مقصد است.
فرض کنید به صورت تجربی مشاهده کرده‌ایم که اگر تنها یک شهر به تعداد شهرهای نقشه اضافه شود الگوریتم الف به دو برابر زمان برای حل مسئله نیاز دارد در حالی که زمان مورد نیاز برای الگوریتم ب وقتی دو برابر می‌شود که تعداد شهرهای نقشه دو برابر شده باشد. بدیهی است که در چنین شرایطی الگوریتم ب را کاراتر از الگوریتم الف می‌دانیم.
در نظریه پیچیدگی محاسباتی نیز همین روش را پی‌می‌گیریم ولی به جای روش‌های تجربی از روش‌های ریاضی استفاده می‌کنیم. به این منظور ابتدا برای ورودی مسئله یک اندازه تعریف می‌کنیم. این اندازه می‌تواند میزان حافظهٔ مورد نیاز برای ذخیره کردن ورودی مسئله باشد. سپس زمان (یا فضای) مورد نیاز برای حل مسئله توسط یک الگوریتم به صورت تابعی از اندازهٔ مسئله محاسبه می‌شود. به محاسبه یا تقریب زدن این چنین تابعی تحلیل الگوریتم گفته می‌شود.
در تحلیل الگوریتم‌ها بهترین، بدترین و متوسط زمان اجرا بررسی می‌شود. هرچند معمولاً بهترین زمان اجرای آن اهمیت ندارد؛ زیرا اساساً به‌ازای ورودی‌های غیر محتمل این حالت رخ می‌دهد. لیکن لازم است الگوریتم‌ها را در بدترین حالت و در صورت امکان در حالت میانگین تحلیل و بررسی کنیم. ممکن است پیچیدگی الگوریتم در یک حالت میانگین بهتر از پیچیدگی‌اش دربدترین حالت باشد و این اطلاعات مفیدی در مورد آن الگوریتم است.
الگوریتم‌ها به دو دسته تقسیم می‌شوند، بازگشتی و ترتیبی. الگوریتم‌های ترتیبی را معمولاً با شمارش دفعات اجرای دستوری که بر اساس اندازه دادهٔ ورودی، بیشترین بار اجرا می‌شود، (در صورتی که زمان اجرای دستور از یک مقدار ثابت تبعیت کند) تحلیل می‌کنیم. اما زمان اجرا و الگوریتم بازگشتی با رابطه‌های بازگشتی بیان می‌شوند. روش‌های مختلفی برای حل این نوع رابطه‌ها داریم. یک روش خوب برای حل رابطه‌های بازگشتی، استفاده از درخت بازگشتی است. این روش نحوه جایگذاری یک عبارت بازگشتی و نیز مقدار ثابتی را که در هر سطح از آن عبارت به دست می‌آید، نشان می‌دهد. حاصل جمع مقادیر ثابت تمام سطرها جواب حل بازگشتی است.
برای بررسی خوب بودن یک الگوریتم، باید به آهنگ رشد منحنی زمان اجرا-اندازه ورودی یا میزان حافظه مصرفی-اندازه ورودی توجه کنیم. برای بررسی دقیق‌تر به بررسی شاخص‌های تحلیل الگوریتم و تعریف توابع رشد می‌پردازیم.
همان‌طور که در بالا گفته شد، تحلیل الگوریتم به معنای تخمین میزان منابعی است که الگوریتم به آن نیاز دارد. فرض می‌کنیم با یک تک پردازندهٔ عمومی پیاده‌سازی شده با حافظه دسترسی تصادفی (RAM) طرف هستیم و الگوریتم پیاده‌سازی شدهٔ ما توسط برنامهٔ کامپیوتری، عملیات‌ها را هم‌زمان انجام نمی‌دهد. در مدل RAM دستورات تعریف شده‌ای وجود دارند که اجرا کردن‌شان از یک مقدار ثابتی تبعیت می‌کند، دستورهایی که در ساختار کامیپوتر تعبیه شده‌اند: مانند عملگرهای حسابی (جمع و تقسیم و ضرب و غیره)، علمیات‌های انتقال اطلاعات (ذخیره کردن، رونویسی کردن حافظه، بازخوانی حافظه و غیره) و عملیات‌های کنترل (فراخوانی توابع، بازگشتن‌از دستور و غیره).
شبه کد زیر که الگوریتم مرتب‌سازی حبابی را پیاده‌سازی می‌کند در نظربگیرید: for i=1 to A.length زمان اجرای الگوریتم، جمع زمان اجرای هر دستوری است که اجرا می‌شود. اگر زمان اجرای هر خط را (که گفتیم مقداری ثابت است) با formula_3 نشان دهیم و اگر formula_4 را زمان کل دستورات خط ۱ تا ۴ در نظر بگیریم، زمان اجرای کل برنامه برابر جمع زمان کل اجرای دستورات هر خط می‌شود.
برای خط اول: formula_5
برای خط دوم: formula_6
برای خط سوم: formula_7 و خط چهارم هم در بدترین حالت (اگر هر دفعه وارد if شود) formula_8 است. پس زمان اجرای کل برنامه در بدترین حالت:
است.
طبق تعریفی که در قسمت تابع formula_10 خواهیم گفت، با وجود داشتن formula_11 و درست بودن رابطه formula_12 برای هر formula_13 خواهیم دید که الگوریتم بالا formula_14 است.
بنا به تعریف، هر الگوریتمی که نوسان رفتاری کمتری از خود نشان دهد، اصطلاحاً از نظر محاسباتی باثبات‌تر است. نظر به این تعریف، دو موضوع تعیین‌کنندهٔ میزان ثبات محاسباتی الگوریتم خواهند بود:
برای سنجش میزان ثبات زمانی، می‌توان از شاخص formula_15 (و یا formula_16) استفاده کرد. مسلماً الگوریتمی از نظر محاسباتی باثبات‌تر است که واریانس formula_15ها کمتر باشد. روش دیگری که می‌توان میزان ثبات زمانی دو یا چند الگوریتم را مقایسه کرد، آن است که با استفاده از آزمون نیکویی بَرازش بررسی کنیم که مقادیر formula_15ها مربوط به کدام الگوریتم، در بازهٔ formula_19، به توزیع یکنواخت نزدیک‌تر است.
در این باب چند نکته مدنظر است:
به‌طور مشابه، برای سنجش میزان ثبات الگوریتم در کیفیت جواب نهایی می‌توان واریانس کیفیت جواب‌های الگوریتم را بعد از چند بار اجرا، اندازه گرفت؛ بنابراین، می‌توان قواعد نکتهٔ قبل را برای این نوع ثبات هم بیان کرد. واضح است که بهترین عملکرید برای ثبات کیفیت جواب نهایی را الگوریتم‌های دقیق دارند.
مسلماً هر الگوریتمی که سریع‌تر همگرا شود، مطلوب‌تر است. این نکته دربارهٔ الگوریتم‌ها دقیق کاملاً صادق است اما دربارهٔ الگوریتم‌های تقریبی باید نرخ همگرایی با احتیاط بیشتری بررسی شود. زیرا ممکن است الگوریتم A در مدت زمان کوتاه‌تری در مقایسه با الگوریتم B به یک نقطهٔ بهینهٔ محلی همگرا شود، اما در عوض الگوریتم B به یک جواب بهینهٔ سراسری همگرا شود. برای بررسی همگرایی که به تنهایی خود یک مقولهٔ جداست به تبیین تعاریف زیر می‌پردازیم:
اگر الگوریتمی بدین‌صورت باشد که اگر با هر نقطهٔ آغازین دلخواهی شروع شود و در نهایت به یک جواب مشخص برسد، آن را همگراشوندهٔ سراسری می‌نامند. از این نوع الگوریتم‌ها می‌توان به الگوریتم غیر مرکب (سیمپلکس) اشاره کرد.
فرض کنید الگوریتم A با شروع از جواب اولیهٔ formula_31، دنبالهٔ جواب‌های formula_32، formula_33، ... را تا همگرا شدن به جواب formula_34 تولید کند که formula_34 می‌تواند جواب بهینهٔ محلی یا سراسری باشد. به عبارت دیگر، می‌توانیم الگوریتم را معادل یک تابع در نظر بگیریم که:
formula_36
در این صورت مرتبهٔ همگرایی بزرگترین عدد حقیقی نامنفی مانند formula_37 است که به‌ازای آن حاصل حد زیر عددی متناهی و نامنفی شود:
formula_38 داده‌ساختار اولیه و formula_39 داده‌ساختار ما بعد از عمل formula_40ام باشد. همچنین فرض کنید که formula_41 هزینهٔ واقعی عمل formula_40ام است. در این صورت تابع پتانسیل formula_43 را تعریف می‌کنیم که formula_39 را به یک عدد حقیقی نگاشت می‌کند. همچنین formula_45 را مطابق فرمول زیر تعریف می‌کنیم:
formula_46
و آن را هزینهٔ سرشکن شدهٔ عمل formula_40ام می‌نامیم.
در این صورت داریم: formula_48
اگر formula_49، داریم: formula_50
یعنی formula_51 کران بالایی برای formula_52 است که می‌خواهیم بدست آوریم.
با نیم‌نگاهی به روش حساب‌داری می‌توان چنین تناظری میان آن و روش تابع پتانسیل برقرار کرد:
یک شمارندهٔ formula_21 بیتی درنظر بگیرید که در ابتدا صفر است. با هر مرحله افزایش حداکثر یک بیت آن از ۰ به ۱ تغییر می‌کند و تعدادی از بیت‌ها نیز از ۱ به ۰ تغییر خواهند داشت. هزینهٔ دقیق این عملیات، متناسب با تعداد تغییر بیت‌ها در شمارنده خواهد بود. فرض کنید بیت‌ها به ترتیب ارزش از formula_65 تا formula_66 شماره گذاری شده باشند. در این‌صورت خواهیم داشت:
بیت ۰: با هر افزایش تغییر می‌کند یعنی در مجموع formula_20 بار.
بیت ۱: یک در میان تغییر می‌کند یعنی در مجموع formula_68 بار.
بیت formula_40: در مجوع دقیقاً formula_70 بار تغییر می‌کند.
تعداد تغییرات بیت‌ها: formula_71
پس هزینهٔ سرشکن شدهٔ هر عمل افزایش، formula_72 است.
در این روش formula_43 را برابر تعداد عناصر موجود در پشته می‌گیریم. بدیهتاً در ابتدا این مقدار صفر بوده تا پایان مجموع عملیات‌ها مقداری مثبت خواهد داشت.
اکنون هزینهٔ سرشکن شده را بدست می‌آوریم:
Push: چون یک عنصر اضافه می‌شود داریم:
formula_74
از طرفی چون می‌دانیم که هزینهٔ درج واقعی formula_75 است پس:
formula_76
Pop: چون یک عنصر کم می‌شود داریم:
formula_77
هزینهٔ واقعی حذف هم formula_78 است پس formula_79
Multi-Pop: چون تعدادی عمل Pop است پس هزینهٔ آن نیز صفر می‌باشد.
بنابراین چون
formula_80
هزینهٔ سرشکن شده formula_72 است.
آنچه که در بالا مطرح شد، شاخص‌هایی بود برای تحلیل عادی الگوریتم‌ها به کار می‌رفت؛ لیکن الگوریتم‌هایی هستند دوگانه (هیبریدی) که حل آن‌ها ابتکاری یا فرا ابتکاری محسوب می‌شود و رسیدن به آن‌ها از چارچوب یک تحلیل ریاضیاتی ساده و به‌کار بردن الگوریتم‌های آشنا خارج است که می‌توان به نمونه‌هایی از آن‌ها اشاره کرد: