تحلیل الگوریتم‌ها

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

در علم کامپیوتر، تجزیه و تحلیل الگوریتم تعیین مقداری از منابع است (مانند زمان و ذخیره سازی) که لازم است آنها را اجرا کند. اکثر الگوریتم‌های طراحی شده برای کار با ورودی‌های با طول اختیاری تولید می‌شوند معمولا بازده و یا در حال اجرا بودن یک الگوریتم است که به عنوان یک تابع در رابطه با طول ورودی معین را به تعداد مراحل اعلام کرد (پیچیدگی زمانی) و یا مکان‌های ذخیره سازی (پیچیدگی فضا). تجزیه و تحلیل الگوریتم بخشی مهم از تئوری پیچیدگی محاسباتی گسترده تر است، که فراهم می‌کند برآوردهای نظری برای منابع مورد نیاز هر الگوریتم که حل با توجه به محاسبات مشکل است این برآوردها ارائه بینشی به جهت معقول برای جستجوی الگوریتم‌های کارآمد است.

در تجزیه و تحلیل نظری الگوریتم آن که مشترک است به منظور برآورد پیچیدگی خود در معنای تقریبی به عنوان مثال، به منظور برآورد تابع پیچیدگی برای ورودی خودسرانه بزرگ. نماد O بزرگ، امگا و تتا برای این منظور استفاده می‌شود. مثلا گفته می‌شود، جستجوی دودویی به اجرا در تعدادی از مراحل، متناسب با لگاریتم طول این لیست در حال جستجو و یا در (O(log(n). معمولا تخمین‌های تقریبی استفاده می‌شود چرا که پیاده سازی‌های مختلف از همان الگوریتم ممکن در کارایی متفاوت است. با این حال بازده هر دو "منطقی" پیاده سازی یک الگوریتم داده شده ضرب در یک ضریب ثابت به نام ثابت مخفی مرتبط است.

اغلب مهم است که بدانید برای چه مقدار از یک منبع خاص (مثل زمان یا حافظه) تئوری مورد نیاز برای یک الگوریتم داده شده. روش‌ها برای تجزیه و تحلیل الگوریتم‌های توسعه یافته برای به دست آوردن مقادیر کمی (تخمین)؛به عنوان مثال، الگوریتم مرتب سازی در بالای یک زمان مورد نیاز از (O(N، با استفاده از نماد گذاری O بزرگ با n به عنوان طول لیست در تمام زمانها در الگوریتم باید دو مقدار را به خاطر داشته باشید: بیشترین تعداد تا کنون و موقعیت فعلی در لیست ورودی. لذا گفته شده است که فضای مورد نیاز از (۱)O است در صورتی که برای ذخیره، شماره‌های ورودی شمارش نمی‌شود یا (O(n آن شمارش شده.

کارایی الگوریتم

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

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

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

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

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

منابع

[۱]