تحلیل الگوریتم‌ها: تفاوت میان نسخه‌ها

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

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

همان طور که در بالا گفته شد، تحلیل الگوریتم به معنای تخمین میزان منابعی است که الگوریتم به آن نیاز دارد. فرض میکنیم با یک تک پردازنده‌ی عمومی پیاده سازی شده با حافظه دسترسی تصادفی (RAM) طرفیمطرف هستیم و الگوریتم پیاده‌سازی شده‌ی ما توسط برنامه‌ی کامپیوتری، عملیات‌ها را همزمان انجام نمی‌دهد. در مدل RAM  دستورات تعریف شده‌ای وجود دارند که اجرا کردن‌شان از یک مقدار ثابتی تبعیت میکند، دستوراتی که در ساختار کامیپوتر تعبیه شده‌اند. مثل عملگرهای حسابی (جمع و تقسیم و ضرب و غیره)، علمیات‌های انتقال اطلاعات (ذخیره کردن، رونویسی کردن حافظه، بازخوانی حافظه و غیره) و عملیات‌های کنترل (فراخوانی توابع، بازگشتن‌از دستور و غیره).<ref> 2.2 ,CLRS, Analyzing Algorithm </ref>

& T_2= \left[ 1+2+3+\cdots + (n-1) + n\right].c_2=&\left[\frac{1}{2}(n^2 + n)\right]c_2\\

:<math>f(n) =T_1+T_2+T_3+T_4= nc_1+\left[ \frac{1}{2} (n^2 + n) \right] c_2 + \left[ \frac{1}{2} (n^2 + n) \right] c_3 + \left[ \frac{1}{2} (n^2 + n) \right] c_4 + (n)c_1