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

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

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

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