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

 

در این باب چند نکته مدنظر است:

* یک عقیده این است که به‌جای بررسی واریانس زمان هر تکرار، واریانس زمان خاتمهٔ الگوریتم را در نظر بگیریم. در این صورت، الگوریتم‌های قطعی، دارای ایده‌آل‌ترین میزان ثبات زمانی هستند، زیرا همیشه مدت زمان اجرای آن‌ها، روی یک سری از داده‌های ورودی معین، یک عدد ثبات است؛ بنابراین، واریانس زمان خاتمهٔ آن‌ها، همواره صفر است.

* اگر یک الگوریتم غیرقطعی را <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> باشه، به شرطی می‌گوییم این الگوریتم داریا ثبات زمانی است که: