موضوع مقاله: تحلیل سرشکن شده | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # تحلیل سرشکن شده | مقدمه: اگر روی یک توالی از اعمال میانگین گرفته شود، هر چند ممکن است یک عمل در داخل آن توالی پرهزینه باشد، اما با استفاده از تحلیل سرشکن شده می‌توان نشان داد که هزینه میانگین عمل کم است. | ## بخش 1: تحلیل سرشکن شده | تحلیل سرشکن شده با تحلیل حالت میانگین که در آن احتمال در نظر گرفته نمی‌شود تفاوت دارد؛ تحلیل سرشکن شده میانگین کارایی هر عمل در بدترین حالت را ضمانت می‌کند. بعلاوه دیدگاهی که با انجام یک تحلیل سرشکن شده نسبت به یک ساختمان داده خاص بدست می‌آید، می‌تواند به بهینه سازی طراحی کمک کند. بنابراین در بدترین حالت، هزینه میانگین، یا هزینه سرشکن شده برای هر عمل برابر است. این هزینه سرشکن شده برای هر عمل به کار می‌رود، حتی وقتی که چندین نوع عمل در توالی وجود داشته باشند. دو روش دیگر، روش حسابداری و روش پتانسیل، ممکن است هزینه‌های سرشکن شده متفاوتی به انواع متفاوت عمل‌ها نسبت دهند. روش حسابداری در روش حسابداری accounting method از تحلیل سرشکن شده، به عمل‌های متفاوت هزینه‌های متفاوتی اختصاص می‌دهیم، به طوری که به تعدادی از اعمال هزینه بیشتر و به تعدادی هزینه کمتری نسبت به هزینه واقعی آن‌ها اختصاص داده می‌شود. هنگامی که هزینه سرشکن شده یک عمل از هزینه واقعی آن تجاوز کند، اختلاف هزینه به عنوان موجودی به اشیایی مشخص در ساختمان داده اختصاص می‌یابد. موجودی بعداً می‌تواند در جهت کمک به پرداخت برای اعمالی که هزینه سرشکن شده آنها کمتر از هزینه واقعی شان است مورد استفاده قرار گیرد. | ## بخش 2: تحلیل سرشکن شده | بنابراین می‌توان هزینه سرشکن شده یک عمل را مشاهده کرد که بین هزینه واقعی آن و موجودی که پرداخت شده یا استفاده می‌شود، تقسیم شده‌است. این روش با تحلیل جمعی که در آن تمام اعمال هزینه‌های سرشکن شده یکسانی دارند، بسیار متفاوت است. اگر بخواهیم تحلیل را با هزینه‌های سرشکن شده انجام دهیم تا نشان دهیم که در بدترین حالت هزینه میانگین هر عمل کم است، کل هزینه سرشکن شده یک توالی از اعمال باید یک حد بالا برای هزینه کل واقعی توالی باشد. علاوه بر این همانند تحلیل جمعی، این رابطه باید برای تمام توالی‌های اعمال برقرار باشد. اگر هزینه واقعی امین عمل را با و هزینه سرشکن شده امین عمل را با نشان دهیم، برای تمام توالی‌هایی از عمل نیاز داریم بنا به نامساوی بالا کل موجودی مربوط به ساختمان داده باید در همه زمان‌ها نامنفی باشد. اگر کل موجودی می‌توانست منفی باشد(در نتیجه پرداخت ارزش کم به عمل‌های قبلی، با این تعهد که دوباره پس از آن پرداخت صورت گیرد) آنگاه کل هزینه‌های سرشکن شده ایجاد شده در آن هنگام کمتر از کل هزینه‌های واقعی ایجاد شده می‌بود؛ برای توالی عمل‌ها تا آن زمان کل هزینه سرشکن شده یک حد بالا برای کل هزینه واقعی نمی‌بود. روش پتانسیل به جای نمایش کار از پیش پرداخت شده به صورت موجودی، که با اشیایی مشخص در ساختمان داده ذخیره می‌شود، روش پتانسیل potential method از تحلیل سرشکن شده، کار از پیش پرداخته شده را به صورت “انرژی پتانسیل” یا تنها “پتانسیل” نمایش می‌دهد که می‌تواند جهت پرداخت برای اعمال آینده آزاد شود. پتانسیل به جای آنکه به اشیای خاص در داخل ساختمان داده اختصاص داده شود، به کل ساختمان داده اختصاص داده می‌شود. | ## بخش 3: تحلیل سرشکن شده | برای هر ، را هزینه واقعی امین عمل قرار می‌دهیم و را ساختمان داده‌ای که پس از به کارگیری امین عمل روی ساختمان داده حاصل می‌شود، قرار می‌دهیم. هزینه سر شکن شده مربوط به امین عمل با توجه به تابع پتانسیل به صورت زیر تعریف می‌شود بنابراین هزینه سرشکن شده هرعمل برابرهزینه واقعی آن به علاوه افزایش پتانسیل حاصل از عمل می‌باشد. بنا به معادله بالا، هزینه سرشکن شده کل عمل برابر است با اگر بتوانیم یک تابع پتانسیل تعریف کنیم بطوریکه ، آنگاه هزینه سرشکن شده کل ، یک حد بالا برای هزینه واقعی کل می‌باشد. بنابراین اگر برای تمام ها تأکید کنیم که، آنگاه همانند روش حسابداری تضمین می‌کنیم که از پیش هزینه را پرداخت کرده‌ایم. به‌طور شهودی اگر اختلاف پتانسیل از امین عمل مثبت باشد آنگاه هزینه سرشکن شده یک پرداخت اضافه به امین عمل را نشان می‌دهد، و پتانسیل ساختمان داده افزایش می‌یابد. اگر اختلاف پتانسیل منفی باشد، آنگاه هزینه سرشکن شده، یک پرداخت کم به امین عمل را نشان می‌دهد و هزینه واقعی عمل با کاهش پتانسیل پرداخت می‌شود. هزینه‌های سر شکن شده تعریف شده به وسیله دو معادلهٔ بالا به انتخاب تابع پتانسیل بستگی دارد. توابع پتانسیل متفاوت ممکن است به هزینه‌های سرشکن شده متفاوت که همچنان حدود بالا برای هزینه‌های واقعی اند منجر گردند. | ## جمع‌بندی | اغلب در انتخاب یک تابع پتانسیل مبادلاتی می‌توانند انجام گیرند؛ بهترین تابع پتانسیل جهت استفاده بستگی به حدود زمانی مطلوب دارد.