تحلیل سرشکن شده کیست؟ توضیح بده.
در تحلیل سرشکن شده ، زمان مورد نیاز جهت انجام یک سلسله از اعمال ساختمان داده ای روی تمام اعمالی که انجام شده‌اند، میانگین گرفته می‌شود. اگر روی یک توالی از اعمال میانگین گرفته شود، هر چند ممکن است یک عمل در داخل آن توالی پرهزینه باشد، اما با استفاده از تحلیل سرشکن شده می‌توان نشان داد که هزینه میانگین عمل کم است. تحلیل سرشکن شده با تحلیل حالت میانگین که در آن احتمال در نظر گرفته نمی‌شود تفاوت دارد؛ تحلیل سرشکن شده میانگین کارایی هر عمل در بدترین حالت را ضمانت می‌کند. بعلاوه دیدگاهی که با انجام یک تحلیل سرشکن شده نسبت به یک ساختمان داده خاص بدست می‌آید، می‌تواند به بهینه سازی طراحی کمک کند. در زیر سه تکنیک رایج که در این تحلیل استفاده می‌شوند پوشش داده شده‌است:تحلیل جمعی.در تحلیل جمعی نشان می‌دهیم که به ازای تمام formula_1ها، یک توالی از formula_1 عمل در مجموع، زمان formula_3 را در بدترین حالت صرف می‌کند. بنابراین در بدترین حالت، هزینه میانگین، یا هزینه سرشکن شده برای هر عمل برابرformula_4 است. این هزینه سرشکن شده برای هر عمل به کار می‌رود، حتی وقتی که چندین نوع عمل در توالی وجود داشته باشند. دو روش دیگر، روش حسابداری و روش پتانسیل، ممکن است هزینه‌های سرشکن شده متفاوتی به انواع متفاوت عمل‌ها نسبت دهند.روش حسابداری.در روش حسابداری از تحلیل سرشکن شده، به عمل‌های متفاوت هزینه‌های متفاوتی اختصاص می‌دهیم، به طوری که به تعدادی از اعمال هزینه بیشتر و به تعدادی هزینه کمتری نسبت به هزینه واقعی آن‌ها اختصاص داده می‌شود. مقدار هزینه‌ای که به یک عمل می‌دهیم، هزینه سرشکن شده آن عمل نامیده می‌شود. هنگامی که هزینه سرشکن شده یک عمل از هزینه واقعی آن تجاوز کند، اختلاف هزینه به عنوان موجودی به اشیایی مشخص در ساختمان داده اختصاص می‌یابد. موجودی بعداً می‌تواند در جهت کمک به پرداخت برای اعمالی که هزینه سرشکن شده آنها کمتر از هزینه واقعی شان است مورد استفاده قرار گیرد. بنابراین می‌توان هزینه سرشکن شده یک عمل را مشاهده کرد که بین هزینه واقعی آن و موجودی که پرداخت شده یا استفاده می‌شود، تقسیم شده‌است. این روش با تحلیل جمعی که در آن تمام اعمال هزینه‌های سرشکن شده یکسانی دارند، بسیار متفاوت است.هزینه‌های سرشکن شده اعمال باید به دقت انتخاب شوند. اگر بخواهیم تحلیل را با هزینه‌های سرشکن شده انجام دهیم تا نشان دهیم که در بدترین حالت هزینه میانگین هر عمل کم است، کل هزینه سرشکن شده یک توالی از اعمال باید یک حد بالا برای هزینه کل واقعی توالی باشد. علاوه بر این همانند تحلیل جمعی، این رابطه باید برای تمام توالی‌های اعمال برقرار باشد. اگر هزینه واقعی formula_5 امین عمل را با formula_6 و هزینه سرشکن شده formula_5 امین عمل را با formula_8 نشان دهیم، برای تمام توالی‌هایی از formula_1 عمل نیاز داریمformula_10بنا به نامساوی بالا کل موجودی مربوط به ساختمان داده باید در همه زمان‌ها نامنفی باشد. اگر کل موجودی می‌توانست منفی باشد(در نتیجه پرداخت ارزش کم به عمل‌های قبلی، با این تعهد که دوباره پس از آن پرداخت صورت گیرد) آنگاه کل هزینه‌های سرشکن شده ایجاد شده در آن هنگام کمتر از کل هزینه‌های واقعی ایجاد شده می‌بود؛ برای توالی عمل‌ها تا آن زمان کل هزینه سرشکن شده یک حد بالا برای کل هزینه واقعی نمی‌بود. بنابراین باید مراقب باشیم تا موجودی کل در ساختمان داده هرگز منفی نشود.روش پتانسیل.به جای نمایش کار از پیش پرداخت شده به صورت موجودی، که با اشیایی مشخص در ساختمان داده ذخیره می‌شود، روش پتانسیل از تحلیل سرشکن شده، کار از پیش پرداخته شده را به صورت “انرژی پتانسیل” یا تنها “پتانسیل” نمایش می‌دهد که می‌تواند جهت پرداخت برای اعمال آینده آزاد شود. پتانسیل به جای آنکه به اشیای خاص در داخل ساختمان داده اختصاص داده شود، به کل ساختمان داده اختصاص داده می‌شود. روش پتانسیل به صورت زیر کار می‌کند. با یک ساختمان داده اولیه formula_11 را شروع می‌کنیم که روی آن formula_1 عمل انجام می‌شود. برای هر formula_13، formula_14 را هزینه واقعی formula_5 امین عمل قرار می‌دهیم و formula_16 را ساختمان داده‌ای که پس از به کارگیری formula_5 امین عمل روی ساختمان داده formula_18 حاصل می‌شود، قرار می‌دهیم. تابع پتانسیلformula_19 هر ساختمان داده formula_16 را به یک عدد حقیقی formula_21 نگاشت می‌کند. این عدد، پتانسیل مربوط به ساختمان دادهٔ formula_16 است. هزینه سر شکن شده formula_8 مربوط به formula_24 امین عمل با توجه به تابع پتانسیل formula_19 به صورت زیر تعریف می‌شودformula_26بنابراین هزینه سرشکن شده هرعمل برابرهزینه واقعی آن به علاوه افزایش پتانسیل حاصل از عمل می‌باشد. بنا به معادله بالا، هزینه سرشکن شده کل formula_1 عمل برابر است باformula_28اگر بتوانیم یک تابع پتانسیل formula_19 تعریف کنیم بطوریکه formula_30، آنگاه هزینه سرشکن شده کل formula_31، یک حد بالا برای هزینه واقعی کل formula_32 می‌باشد. در عمل همواره نمی‌دانیم چه تعداد عمل ممکن است انجام شود. بنابراین اگر برای تمام formula_5ها تأکید کنیم کهformula_34، آنگاه همانند روش حسابداری تضمین می‌کنیم که از پیش هزینه را پرداخت کرده‌ایم. اغلب مناسب است که formula_35 را formula_36 تعریف کنیم و آنگاه نشان دهیم که برای تمام formula_5ها، formula_38.به‌طور شهودی اگر اختلاف پتانسیل formula_39 از formula_5 امین عمل مثبت باشد آنگاه هزینه سرشکن شده formula_41 یک پرداخت اضافه به formula_5 امین عمل را نشان می‌دهد، و پتانسیل ساختمان داده افزایش می‌یابد. اگر اختلاف پتانسیل منفی باشد، آنگاه هزینه سرشکن شده، یک پرداخت کم به formula_5 امین عمل را نشان می‌دهد و هزینه واقعی عمل با کاهش پتانسیل پرداخت می‌شود.هزینه‌های سر شکن شده تعریف شده به وسیله دو معادلهٔ بالا به انتخاب تابع پتانسیل formula_19 بستگی دارد. توابع پتانسیل متفاوت ممکن است به هزینه‌های سرشکن شده متفاوت که همچنان حدود بالا برای هزینه‌های واقعی اند منجر گردند. اغلب در انتخاب یک تابع پتانسیل مبادلاتی می‌توانند انجام گیرند؛ بهترین تابع پتانسیل جهت استفاده بستگی به حدود زمانی مطلوب دارد.منابع.کتاب CLRS