ادامه بحث آنالیز

خب بحث انواع آنالیز‌ها رو ادامه بدیم.

خب مشکلات آنالیز تجربی رو گفتیم. راه حل‌هاشم گفتیم. حالا بریم ببینیم باید چیکار کنیم.

عبارتی مثل انتساب مقدار به یک متغییر رو در نظر بگیرین.

a = 10

این عبارت سطح بالا به تعدادی مشخص از عملیات‌های سطح پائین تبدیل میشه. یا عبارتی مثل:

data[i]

باز هم در سطوح پائین تر به یه تعداد مشخصی از operation ها تبدبل میشه. و خب میشه هر برنامه ای رو به این عبارت های اولیه شکست چون هر برنامه در واقع تعداد مشخصی از عبارت‌های اولیه است. مثلا با حلقه for چند عبارت اولیه رو چندین بار تکرار میکنیم. پس در همین سطح بالایی هم که هستیم برنامه‌های ما چیزی نیستن جز مجموعه‌ای از primitive operation ها. چیزی که الان به ذهنمون میرسه اینه که تعداد این primitive operation ها رو اندازه بگیریم و مثلا اون رو t بنامیم. این t رو به عنوان یه رویکرد سطح بالا برای اندازه‌گیری زمان اجرای الگوریتم در نظر میگیریم. اینجا دقت کنین که مثلا عبارت:

a = 10

به تعداد مشخصی operation در سطوح پائین تبدیل میشه و :

data[0]

هم به تعداد مشخصی تبدیل میشه. ولی اینها تعداد مساوی ندارن. ولی ما وقتی جمعشون کردیم و به t رسیدیم فرضمون این بوده که اینها در زمان یکسان اجرا میشن. یعنی تعداد operation های سطح پایین یکسان و یک نوعی رو تولید میکنن. این فرض تاثیر چندانی در آنالیز ما نداره و اینجا برای سادگی ما اینجور فرض کردیم و این با ارزشه.

خب حالا که ما t رو داریم، در واقع یه رودیکرد سطح بالا داریم. میتونیم t رو به عنوان زمان اجرای الگوریتم اعلام کنیم. البته اینجا ممکنه یکم گیج بشیم. چرا که داریم راجع به زمان حرف می‌زنیم در صورتی که t از جنس زمان نیست. رویکرد سطح بالای ما در واقع داره تعداد primitive operation ها رو میگه و این تو هر کامپیوتری صادقه‌. حالا دیگه رو هر کامپیوتری میایم حساب میکنیم که اون کامپیوتر هر operation رو در چه زمانی انجام میده و با یع تناسب ساده میتونیم زمان اجرا رو به دست بیاریم. (**حقیقتش من درست نمیدونم تعداد operation بر ثانیه درسته یا تعداد instruction بر ثانیه**). اینجا دیگه ما نیازی نیست که برای مطالعه الگوریتم حتما اونو implement کنیم، میتونیم از psudo code استفاده کنیم. پس ما به هدفمون که ایجاد یک رویکرد سطح بالا بدون implement کردن و مستقل از ویژگی‌های سخت افزاری و نرم‌افزاری بود رسیدیم. تو قسمت بعد از این روش استفاده می‌کنیم و انواع دیگه آنالیز رو باهاش انجام میدیم.