تحلیل سرشکن شده
در تحلیل سرشکن شده ، زمان مورد نیاز جهت انجام یک سلسله از اعمال ساختمان داده ای روی تمام اعمالی که انجام شدهاند، میانگین گرفته میشود. اگر روی یک توالی از اعمال میانگین گرفته شود، هر چند ممکن است یک عمل در داخل آن توالی پرهزینه باشد، اما با استفاده از تحلیل سرشکن شده میتوان نشان داد که هزینه میانگین عمل کم است. تحلیل سرشکن شده با تحلیل حالت میانگین که در آن احتمال در نظر گرفته نمیشود تفاوت دارد؛ تحلیل سرشکن شده میانگین کارایی هر عمل در بدترین حالت را ضمانت میکند. بعلاوه دیدگاهی که با انجام یک تحلیل سرشکن شده نسبت به یک ساختمان داده خاص بدست میآید، میتواند به بهینه سازی طراحی کمک کند. در زیر سه تکنیک رایج که در این تحلیل استفاده میشوند پوشش داده شدهاست:
تحلیل جمعی
در تحلیل جمعی نشان میدهیم که به ازای تمام
روش حسابداری
در روش حسابداری از تحلیل سرشکن شده، به عملهای متفاوت هزینههای متفاوتی اختصاص میدهیم، به طوری که به تعدادی از اعمال هزینه بیشتر و به تعدادی هزینه کمتری نسبت به هزینه واقعی آنها اختصاص داده میشود. مقدار هزینهای که به یک عمل میدهیم، هزینه سرشکن شده آن عمل نامیده میشود. هنگامی که هزینه سرشکن شده یک عمل از هزینه واقعی آن تجاوز کند، اختلاف هزینه به عنوان موجودی به اشیایی مشخص در ساختمان داده اختصاص مییابد. موجودی بعداً میتواند در جهت کمک به پرداخت برای اعمالی که هزینه سرشکن شده آنها کمتر از هزینه واقعی شان است مورد استفاده قرار گیرد. بنابراین میتوان هزینه سرشکن شده یک عمل را مشاهده کرد که بین هزینه واقعی آن و موجودی که پرداخت شده یا استفاده میشود، تقسیم شدهاست. این روش با تحلیل جمعی که در آن تمام اعمال هزینههای سرشکن شده یکسانی دارند، بسیار متفاوت است.
هزینههای سرشکن شده اعمال باید به دقت انتخاب شوند. اگر بخواهیم تحلیل را با هزینههای سرشکن شده انجام دهیم تا نشان دهیم که در بدترین حالت هزینه میانگین هر عمل کم است، کل هزینه سرشکن شده یک توالی از اعمال باید یک حد بالا برای هزینه کل واقعی توالی باشد. علاوه بر این همانند تحلیل جمعی، این رابطه باید برای تمام توالیهای اعمال برقرار باشد. اگر هزینه واقعی
بنا به نامساوی بالا کل موجودی مربوط به ساختمان داده باید در همه زمانها نامنفی باشد. اگر کل موجودی میتوانست منفی باشد(در نتیجه پرداخت ارزش کم به عملهای قبلی، با این تعهد که دوباره پس از آن پرداخت صورت گیرد) آنگاه کل هزینههای سرشکن شده ایجاد شده در آن هنگام کمتر از کل هزینههای واقعی ایجاد شده میبود؛ برای توالی عملها تا آن زمان کل هزینه سرشکن شده یک حد بالا برای کل هزینه واقعی نمیبود. بنابراین باید مراقب باشیم تا موجودی کل در ساختمان داده هرگز منفی نشود.
روش پتانسیل
به جای نمایش کار از پیش پرداخت شده به صورت موجودی، که با اشیایی مشخص در ساختمان داده ذخیره میشود، روش پتانسیل از تحلیل سرشکن شده، کار از پیش پرداخته شده را به صورت “انرژی پتانسیل” یا تنها “پتانسیل” نمایش میدهد که میتواند جهت پرداخت برای اعمال آینده آزاد شود. پتانسیل به جای آنکه به اشیای خاص در داخل ساختمان داده اختصاص داده شود، به کل ساختمان داده اختصاص داده میشود. روش پتانسیل به صورت زیر کار میکند. با یک ساختمان داده اولیه
بنابراین هزینه سرشکن شده هرعمل برابرهزینه واقعی آن به علاوه افزایش پتانسیل حاصل از عمل میباشد. بنا به معادله بالا، هزینه سرشکن شده کل
اگر بتوانیم یک تابع پتانسیل
منابع
کتاب CLRS
پانویس
- ↑ amortized analysis
- ↑ aggregate analysis
- ↑ accounting method
- ↑ potential method
- ↑ potential function
- ↑ potential