تحلیل الگوریتم‌ها: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
ثبات محاسباتی الگوریتم |
|||
خط ۶۶:
=== میزان ثبات محاسباتی ===
بنا به تعریف، هر الگوریتمی که نوسان رفتاری کمتری از خود نشان دهد، اصطلاحا از نظر محاسباتی باثبات‌تر است. نظر به این تعریف، دو موضوع تعیین‌کنندهٔ میزان ثبات محاسباتی الگوریتم خواهند بود:
# ثبات در مدت زمان اجرا (ثبات زمانی)
# ثبات در کیفیت جواب نهایی
برای سنجش میزان ثبات زمانی، می‌توان از شاخص <math>\Delta_{t+1}</math> (و یا <math>\lambda_{s+1}</math>) استفاده کرد. مسلما الگوریتمی از نظر محاسباتی باثبات‌تر است که واریانس <math>\Delta_{t+1}</math>ها کمتر باشد. روش دیگری که می‌توان میزان ثبات زمانی دو یا چند الگوریتم را مقایسه کرد، آن است که با استفاده از آزمون '''نیکویی بَرازش (Goodnes of Fit)''' بررسی کنیم که مقادیر <math>\Delta_{t+1}</math>هیا مربوط به کدام الگوریتم، در بازهٔ <math>(\Delta_{min}, \Delta_{max})</math>، به توزیع یکنواخت نزدیک‌تر است.
در این باب چند نکته مدنظر است:
* آزمون نیکویی برازش را می‌بایست با سطح اطمینان بالا انجام داد و اساسا با اطمینان زیر ۵۰٪ اساسا معنایی ندارد.
* یک عقیده این است که به‌جای بررسی واریانس زمان هر تکرار، واریانس زمان خاتهٔ الگوریتم را در نظربگیریم. در این صورت، الگوریتم‌های قطعی، دارای ایده‌آل‌ترین میزان ثبات زمانی هستند، زیرا همیشه مدت زمان اجرای آن‌ها، روی یک سری از داده‌های ورودی معین، یک عدد ثبات است؛ بنابراین، واریانس زمان خاتمهٔ آن‌ها، همواره صفر است.
* اگر یک الگوریتم غیرقطعی را <math>n</math> بار به‌ازای هر یک از شاخص‌های اندازهٔ <math>k</math> و <math>k+1</math> اجرا کنیم و میانگین و واریانس زمان خاتمهٔ این الگوریتم غیرقطعی به‌ازای اندازه‌های <math>k</math> و <math>k+1</math> به‌ترتیب برابر با <math>(\mu_k,\sigma_k^2)</math> و <math>(\mu_{k+1},\sigma_{k+1}^2)</math> باشه، به شرطی می‌گوییم این الگوریتم داریا ثبات زمانی است که:
# ضریب تغییرات زمان خاتمه در همهٔ اندازه‌ها، دارای یک کران بالای ثابت متناهی مانند <math>c</math> باشد (یعنی <math>\forall_k: \sigma_k / \mu_k \le c</math>) و معمولا <math>c<0.2</math> در نظر می‌گیرند.
# با افزایش اندازه و ابعاد مسئله، واریانس زمان خاتمهٔ الگوریتم* حداکثر به صروت خطی رشد کند.به‌عبارت دیگر، <math>\exists_{a_1, b_1 \in \R}: \sigma_{k+1}^2 \le a_1\sigma_k^2 + b_1</math>
به‌طور مشابه، برای سنجش میزان ثبات الگوریتم در کیفیت جواب نهایی می‌توان واریانس کیفیت جواب‌های الگوریتم را بعد از چند بار اجرا، اندازه گرفت. بنابراین، می‌توان قواعد نکتهٔ قبل را برای این نوع ثبات هم بیان کرد. واضح است که بهترین عملکرید برای ثبات کیفیت جواب نهایی را الگوریتم‌های دقیق دارند.
=== نرخ همگرایی ===
| |||