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

موضوع تحلیل الگوریتم ها تعیین میزان منابعی است که برای اجرای هر الگوریتم لازم است. منابعی مثل زمان، حافظه، پهنای باند ارتباطی، یا سخت افزار رایانه در نظر گرفته می شوند. اکثر الگوریتم های طراحی شده برای کار با ورودی های با طول اختیاری تولید می شوند. کارایی یا پیچیدگی هر الگوریتم را با تابعی نشان می دهند که تعداد مراحل لازم برای اجرای الگوریتم را برحسب طول داده ورودی، یا میزان محل های گرفته شدهٔ حافظه را بر حسب طول داده ورودی نشان می دهد. پیچیدگی زمانی، مقدارپیچیدگی محاسباتی ای را توصیف می کند که در اجرای یک الگوریتم مصرف می شود. غالباً مشاهده می شود که یک مسئله را با استفاده از چندین تکنیک مختلف می توان حل نمود ولی فقط یکی از آن ها به الگوریتمی منجر می شود که از بقیه سریعتر است.
در تجزیه و تحلیل نظری الگوریتم آنچه مشترک است، برآورد پیچیدگی در معنای تقریبی آن است. به عنوان مثال، برآورد تابع پیچیدگی برای ورودی خودسرانه بزرگ. نمادهای O , Θ , Ω برای این منظور استفاده می شوند. مثلاً گفته می شود، جستجوی دودویی به اجرا در Θ ( l o g n ) مرحله تناسب دارد.
معمولاً تخمین های تقریبی استفاده می شوند، چرا که پیاده سازی های مختلف از همان الگوریتم، ممکن است در کارایی متفاوت باشد. با این حال بازده هر دو، با «منطق» پیاده سازی یک الگوریتم داده شده، ضرب در یک ضریب ثابت به نام ثابت مخفی مرتبط است.
در مورد تحلیل الگوریتم باید در مورد موضوعاتی مانند تابع رشد، روش تحلیل الگوریتم های ترتیبی و بازگشتی، حل رابطه های بازگشتی ساده، همگن و نا همگن و همچنین تحلیل سرشکنی صحبت کرد.
در نظریه پیچیدگی محاسباتی، الگوریتم ها از حیث کارایی در استفاده از منابعی مانند زمان و فضا ( حافظه ) مورد بررسی قرار می گیرند. در این بررسی آنچه اهمیت دارد میزان زمان و فضای مورد نیاز برای حل یک مسئلهٔ خاص نیست بلکه چگونگی افزایش میزان زمان و فضای مورد نیاز با بزرگ شدن ورودی الگوریتم مورد توجه است.
مثلاً فرض کنید دو الگوریتم الف و ب برای حل مسئله
فرض کنید به صورت تجربی مشاهده کرده ایم که اگر تنها یک شهر به تعداد شهرهای نقشه اضافه شود الگوریتم الف به دو برابر زمان برای حل مسئله نیاز دارد در حالی که زمان مورد نیاز برای الگوریتم ب وقتی دو برابر می شود که تعداد شهرهای نقشه دو برابر شده باشد. بدیهی است که در چنین شرایطی الگوریتم ب را کاراتر از الگوریتم الف می دانیم.