تفاوت amortized analysis با average case - هفت خط کد انجمن پرسش و پاسخ برنامه نویسی

تفاوت amortized analysis با average case

+1 امتیاز
ما داخل amortized analysis از همه ی عملیات ها میانگین می گیریم برای محاسبه average case هم میانگین می گرفتیم.

یعنی amartized analysis همون محاسبه average case هست؟ یا تفاوتی هم با هم دارند ؟
سوال شده مهر 4, 1393  بوسیله ی َAI (امتیاز 200)   13 19 30

1 پاسخ

0 امتیاز
آره با هم متفاوت هستند .

داخل average case آمار واحتمال هم دخیل هستش

ولی در amortize analysis همون طوری که توی اون لینک هم گفتم باید زمان اجرا  همه ی حالت های ممکن رو با هم جمع بزنید و میانگین بگیرید.

مثلا فرض کنید می خواهید الگوریتم  selection sort رو مرتبه زمانیشو بدست بیارید در اکثر الگوریتم های مرتب سازی اعداد و ترتیبشون هم مهم هستش  چون ما بینهایت عدد و حالت مختلف داریم نمی تونیم بیایم زمان همه اعداد رو محاسبه کنیم و میانگین بگیریم پس amortized analysis این جا کاملا بی معنی هستش ولی برای محاسبه average case میشه  احتمال این که مثلا هر n تا عدد مرتب باشن رو حساب کرد بعد بر اساس این احتمال ها average case الگوریتم رو محاسبه کرد
پاسخ داده شده مهر 5, 1393 بوسیله ی BlueBlade (امتیاز 15,315)   15 18 89
...