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

محتوای حذف‌شده محتوای افزوده‌شده
Sina0k (بحث | مشارکت‌ها)
Sina0k (بحث | مشارکت‌ها)
بدون خلاصۀ ویرایش
برچسب‌ها: ویرایشگر دیداری ویرایش همراه ویرایش از وبگاه همراه
خط ۳۳:
 
 
همان طور که در بالا گفته شد، تحلیل الگوریتم به معنای تخمین میزان منابعی است که الگوریتم به آن نیاز دارد. فرض میکنیم با یک تک پردازنده‌ی عمومی پیاده سازی شده با حافظه دسترسی تصادفی (RAM) طرفیم و الگوریتم پیاده‌سازی شده‌ی ما توسط برنامه‌ی کامپیوتری، عملیات‌ها را همزمان انجام نمی‌دهد. در مدل RAM  دستورات تعریف شده‌ای وجود دارند که اجرا کردن‌شان از یک مقدار ثابتی تبعیت میکند، دستوراتی که در ساختار کامیپوتر تعبیه شده‌اند. مثل عملگرهای حسابی (جمع و تقسیم و ضرب و غیره)، علمیات‌های انتقال اطلاعات (ذخیره کردن، رونویسی کردن حافظه، بازخوانی حافظه و غیره) و عملیات‌های کنترل (فراخوانی توابع، بازگشتن‌از دستور و غیره).<ref> 2.2 ,CLRS, Analyzing Algorithm </ref>
 
الگوریتم مرتب‌سازی حبابی را در نظر بگیرید:
خط ۵۰:
\end{align}</math>
برای خط دوم: <math>\begin{align}
& T_2= \left[ 1+2+3+\cdots + (n-1) + n\right].c_1c_2=&\left[\frac{1}{2}(n^2 + n)\right]c_2\\
\end{align}</math>
 
خط سوم هم مانند خط دوم و خط چهارم هم در بدترین حالت همانند خط دوم، به همان اندازه تکرار می‌شود. پس زمان اجرای کل برنامه در بدترین حالت:
 
:<math>f(n) =T_1+T_2+T_3+T_4= \left[ \frac{1}{2} (n^2 + n) \right] T_2c_2 + \left[ \frac{1}{2} (n^2 + n) \right] T_3c_3 + \left[ \frac{1}{2} (n^2 + n) \right] T_4c_4 + (n)T_1c_1
</math>
 
است.
 
اگر زمان اجرای هر خط را (که گفتیم مقداری ثابت است) با <math>c_1,c_2,c_3,c_4</math> نشان دهیم، طبق تعریفی که در قسمت تابع <math>\mathcal{O}</math> خواهیم گفت، با مقداردهی <math>c = 2(c_1+c_2+c_3+c_4)</math> و <math>n_0 =1</math> خواهیم دید که الگوریتم بالا <math>\mathcal{O}(n^2)</math> است.
 
=== پیچیدگی فضای حافظه ===