- قسمت سوم
• آنالیز حدی (Asymptotic analysis)
در ریاضی ما توابع خطی رو به این فرم مینویسیم:
f(n) = an + b
یعنی تابع ما یک رابطه بین ورودی و خروجی تعریف میکنه. در بحث آنالیز الگوریتم ها باید بدونیم که در حالت کلی با افزایش سایز مسئله(سایز ورودی) زمان اجرای الگوریتم هم بیشتر میشه. ما دوست داریم بتونیم زمان اجرای الگوریتممون رو به صورت یک تابع از ورودی بیان کنیم. مثل مثال بالا. اول چندتا تا نکته رو بگیم:
- درسته که سایز ورودی عامل اصلی هستش ولی دقت کنیم که مثلا اگه یه الگوریتم مرتب سازی داشته باشیم که قرار باشه یه آرایه رو مرتب کنه، نه تنها سایز آرایه مهمه بلکه آرایش عناصر و ترتیب قرارگیری اونها از قبل در آرایه هم مهمه. ممکنه از قبل تقریبا مرتب باشند و فقط نیاز به چند عملیات داشته باشه تا کاملا مرتب بشه. حالا یه آرایه با همون سایز ولی کاملا نامرتب. کاملا مشخصه که تعداد عملیات بیشتر و در نتیجه زمان اجرای بیشتری رو میطلبه. پس: نه تنها سایز وروری مهمه بلکه نوع ورودی هم مهمه
- نکته دوم اینه که ما بدترین حالت رو در نظر میگیریم. یعنی مثلا برای یه آرایه که قراره به صورت صعودی مرتب کنیم فرض میکنیم ترتیب اولیش نزولی باشه.
- نکته سوم اینه که در حالت کلی هرچه اندازه ورودی تابع بزرگ‌تر باشه زمان اجرای الگوریتم بیشتره. اگه تابع مربوط به زمان اجرای یه الگوریتم رو رسم کنیم، معمولا با بزرگ شدن n زمان اجرا هم زیاد میشه. هدف ما اینه که بدونیم این افزایش زمان اجرا به چه صورته؟ یعنی با بزرگ شدن n زمان اجرا چجوری و با چه نسبتی افزایش پیدا میکنه یا به عبارتی نرخ رشد(growth rate) تابع چه جوریه.
تعریف نرخ رشد یا growth rate: نسبت افزایش اندازه ورودی به زمان اجرای تابع
او بزرگ (O): از این نماد برای نشان دادن نرخ رشد تابع استفاده میکنیم و به این صورت تعریفش میکنیم:
اگر f(n) و g(n) دو تابع باشند که اعداد صحیح مثبت رو به اعداد حقیقی مثبت مپ کنند، آنگاه f(n) از O(g(n)) است اگر عدد ثابتی مثل c > 0 و n > a وجود داشته باشد به طوری که:
f(n) <= cg(n) , n >= a
این رو چند جور میشه خوند:
بعضی مواقع ما مینویسیم:
f(n) = O(g(n))
---> باید حواسمون باشه این علامت = اون علامت مساوی که میشناسیم نیست بلکه به جای کلمه is استفاده شده. بهتره همون is رو استفاده کنیم.
f(n) is O(g(n))
یه تعریف دیگه از نماد O بزرگ: بدترین نرخ رشد الگوریتم در بدترین حالت.
خوب که به این جمله نگاه کنیم میبینیم در واقع انگار یه جمله مثبتیه. یعنی O داره به ما میگه که خیالت راحت باشه از این مقدار بیشتر نمیشه. یعنی مثل علامت => (کوچک‌تر یا مساوی) عمل میکنه.
خب خب خب ...
میخوایم یک مثال از دنیای واقعی رو ببینیم و به کمک نماد O ببینم از چه مرتبه‌ای هست. کد زیر رو در نظر بگیریم:
a = 10
b = []
for i in range(N):
b.append(i)
انتساب مقدار ۱۰ به a یک عملیات از مرتبه O(1) است چون در زمان ثابتی انجام میشود. همچنین انتساب [ ] به b هم همینطور. بدنه حلقه for هم یک عملیات از مرتبه O(1) است (البته این یک نوع آنالیز دیگر نیاز دارد که بعدا بررسی میکنیم) و این عملیات ثابت به تعداد N بار تکرار میشود. پس الگوریتم ما از مرتبه O(N) است. اینجا ما عملیات های ثابت رو در نظر نگرفتیم یعنی اینجوری میشه در واقعیت:
f(N) = 1 + 1 + N = 2 + N
حال اگر فرض کنیم N به اندازه کافی بزرگ باشد(به بینهایت میل کند) طبق تعریفی که برای O داشتیم میتونیم بگیم:
f(N) is O(n)
و اینجوریه که نماد O به ما اجازه میده که بتونیم ضرایب ثابت و عملیاتی که در زمان O(1) انجام میشن رو در نظر نگیریم(البته در تحلیل حدی!!!!)
یعنی در واقع عدد ثابت و بزرگ تر از صفری مثل c وجود دارد که به ازای n بزرگ تر از a نمودار cg(n) بالای نمودار f قرار میگیره و f از پایین بهش نزدیک میشه(در بینهایت بهش میل میکنه). این یعنی تقریبا همون علامت => که به این معنیه که مرتبه رشد f از اُردر O(n) است که یه تابع خطی است.
ما به دنبال الگوریتم هایی هستیم که مرتبه رشد اونها n یا log n و یا حداکثر n² باشه. log n خیلی خوبه، n خوبه و n² هم نسبتا قابل قبوله در بعضی مواقع ولی n³ و بالاتر و یا مرتبه نمایی به هیچ وجه به درد نمی‌خورن و به شدت غیر بهینه هستند.
توابعی که زیاد با اونها روبرو میشیم در بحث آنالیز الگوریتم‌ها:
f(n) = c تابع ثابت
f(n) = an + b تابع خطی
f(n) = n² تابع درجه دوم
f(n) = n³ تابع درجه سوم
f(n) = log n تابع لگاریتم
f(n) = n log n
f(n) = a ^ n تابع نمایی
پ.ن:در علوم کامپیوتر معمولا به صورت توافقی وقتی مبنای لگاریتم رو نمینویسیم برخلاف ریاضی که اون رو ۱۰ فرض میکنن ولی توی کتابای کامپیوتر اون رو ۲ در نظر میگیرن. اینجا هم مبنا ۲ هست.
Source : Donald Knuth
