تحلیل سرشکنی

محتویات

۱ تحلیل سرشکنی
۲ منابع
۳ پانویس‌ها

تحلیل سرشکنی [ویرایش]

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

این روش در واقع:

• میانگین اجرای هر عمل در بدترین حالت را بدست می‌دهد.

• مربوط به اجرای کل برنامه‌است نه دستورات خاصی از برنامه.

• در این تحلیل این گونه تفسیر می‌شود که بعضی از دستورات پر هزینه در آینده برای دستوراتی که هزینهٔ کمتری دارند خرج می‌کنند.

در این تحلیل از ۳ روش استفاده می‌شود:

i. روش پتانسیل^[۱]

ii. روش حسابداری^[۲]

iii. روش انبوهه^[۳]

روش انبوهه [ویرایش]

روش اول تحلیل این است که به سادگی هزینهٔ پی در پی اجرای n عملیات را محاسبه کنیم $T(n)$ و آن را بر تعداد (n) تقسیم کرده و در نتیجه هزینهٔ میانگین یا سرشکن شده برای هر عمل بدست می‌آید.برای استفاده از این روش باید هر عمل و هزینهٔ اجرای آن را شناسایی کرد.

$T(n)/n$

روش حسابداری [ویرایش]

در روش حسابداری در ابتدا یک سری عملیات ابتدایی که در الگوریتم مورد استفاده قرار می‌گیرند را انتخاب می‌کنیم و به صورت دلخواه هزینهٔ آن‌ها را ۱ در نظر می‌گیریم.

به هر مجموعه عملیات یک هزینه نسبت داده می‌شود و عملیاتی که هزینهٔ کمتری دارند پولشان برای هزیته‌های بعدی ذخیره می‌شود.

میزان پول پرداختی برای هر عمل با هزینهٔ سرشکنی آن متناسب است.

روش پتانسیل [ویرایش]

راه دیگر پیدا کردن هزینهٔ سرشکنی استفاده از تابع پتانسیل است.در این روش به داده ساختار داده شده یک تابع پتانسیل نسبت می‌دهیم ( $\phi (D_i)$ )و ادعا می‌کنیم که هر عمل در آن ساختار یک هزینهٔ سرشکنی دارد( $\hat c_i$ ) که شامل هزینهٔ واقعی آن می‌شود.

$\hat c_i = c_i + \phi (D_i) - \phi (D_i-1)$

بهتر است که تابع پتانسیل:

۱.منفی نباشد.

۲.ساده باشد.

۳.بازتاب دقیقی از هزینه‌های موجود در داده ساختار(مثلاَ خالی کردن آن) باشد.

تحلیل شمارندهٔ دودویی [ویرایش]

Q۰	Q۱	Q۲	Q۳
۰	۰	۰	۰
۱	۰	۰	۰
۰	۱	۰	۰
۱	۱	۰	۰
۰	۰	۱	۰

روش انبوهه [ویرایش]

برای تحلیل شمارنده بااین روش این گونه در نظر گرفته می‌شود که اگر تغییر بیت‌ها در هر مرحله را در نظر بگیریم در مجموع برابر با ۲n و در نتیجه از $(o(n$ می‌شود.

روش حسابداری [ویرایش]

برای این داده ساختار به ازای هر عمل ۲ ریال هزینه می‌کنیم که این ۲ریال صرف تغییر ۰ به ۱ و بالعکس می‌شود.

روش پتانسیل [ویرایش]

تابع پتانسیلی که در این روش در نظر گرفته می‌شود معادل با تفاوت تعداد ۰ و ۱ها در هر مرحله می‌باشد.( $t_i$ معادل با تعداد بیت‌های تغییر یافته از ۰ به ۱ و بالعکس می‌باشد)