تحلیل سرشکن شده

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

## تحلیل جمعی
در تحلیل جمعی نشان می‌دهیم که به ازای تمام nها، یک توالی از n عمل در مجموع، زمان  T(n) را در بدترین حالت صرف می‌کند. بنابراین در بدترین حالت، هزینه میانگین، یا هزینه سرشکن شده  برای هر عمل برابر T(n)/ n  است. این هزینه سرشکن شده برای هر عمل به کار می‌رود، حتی وقتی که چندین نوع عمل در توالی وجود داشته باشند. دو روش دیگر، روش حسابداری و روش پتانسیل، ممکن است هزینه‌های سرشکن شده متفاوتی به انواع متفاوت عمل‌ها نسبت دهند.

## روش حسابداری
در روش حسابداری  از تحلیل سرشکن شده، به عمل‌های متفاوت هزینه‌های متفاوتی اختصاص می‌دهیم، به طوری که به تعدادی از اعمال هزینه بیشتر و به تعدادی هزینه کمتری نسبت به هزینه واقعی آن‌ها اختصاص داده می‌شود. مقدار هزینه‌ای که به یک عمل می‌دهیم، هزینه سرشکن شده آن عمل نامیده می‌شود. هنگامی که هزینه سرشکن شده یک عمل از هزینه واقعی آن تجاوز کند، اختلاف هزینه به عنوان موجودی به اشیایی مشخص در ساختمان داده اختصاص می‌یابد. موجودی بعداً می‌تواند در جهت کمک به پرداخت برای اعمالی که هزینه سرشکن شده آنها کمتر از هزینه واقعی شان است مورد استفاده قرار گیرد. بنابراین می‌توان هزینه سرشکن شده یک عمل را مشاهده کرد که بین هزینه واقعی آن و موجودی که پرداخت شده یا استفاده می‌شود، تقسیم شده‌است. این روش با تحلیل جمعی که در آن تمام اعمال هزینه‌های سرشکن شده یکسانی دارند، بسیار متفاوت است.
هزینه‌های سرشکن شده اعمال باید به دقت انتخاب شوند. اگر بخواهیم تحلیل را با هزینه‌های سرشکن شده انجام دهیم تا نشان دهیم که در بدترین حالت هزینه میانگین هر عمل کم است، کل هزینه سرشکن شده یک توالی از اعمال باید یک حد بالا برای هزینه کل واقعی توالی باشد. علاوه بر این همانند تحلیل جمعی، این رابطه باید برای تمام توالی‌های اعمال برقرار باشد. اگر هزینه واقعی i امین عمل را با  c_i  و هزینه سرشکن شده i امین عمل را با \hat  c_i  نشان دهیم، برای تمام توالی‌هایی از n عمل نیاز داریم

\sum_{i=1}^n \hat c_i>= \sum_{i=1}^n c_i 

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

## روش پتانسیل
به جای نمایش کار از پیش پرداخت شده به صورت موجودی، که با اشیایی مشخص در ساختمان داده ذخیره می‌شود، روش پتانسیل  از تحلیل سرشکن شده، کار از پیش پرداخته شده را به صورت “انرژی پتانسیل” یا تنها “پتانسیل” نمایش می‌دهد که می‌تواند جهت پرداخت برای اعمال آینده آزاد شود. پتانسیل به جای آنکه به اشیای خاص در داخل ساختمان داده اختصاص داده شود، به کل ساختمان داده اختصاص داده می‌شود. روش پتانسیل به صورت زیر کار می‌کند. با یک ساختمان داده اولیه D_0 را شروع می‌کنیم که روی آن n عمل انجام می‌شود. برای هر i = 1, 2, \cdots , n ، c_i را هزینه واقعی i امین عمل قرار می‌دهیم و D_i را ساختمان داده‌ای که پس از به کارگیری i امین عمل روی ساختمان داده D_{i-1} حاصل می‌شود، قرار می‌دهیم. تابع پتانسیل\phi  هر ساختمان داده D_i را به یک عدد حقیقی \phi(D_i)  نگاشت می‌کند. این عدد، پتانسیل  مربوط به ساختمان دادهٔ D_i است. هزینه سر شکن شده \hat  c_i  مربوط به i  امین عمل با توجه به تابع پتانسیل \phi  به صورت زیر تعریف می‌شود

 \hat c_i = c_i + \phi (D_i) - \phi (D_{i-1})  

بنابراین هزینه سرشکن شده هرعمل برابرهزینه واقعی آن به علاوه افزایش پتانسیل حاصل از عمل می‌باشد. بنا به معادله بالا، هزینه سرشکن شده کل n عمل برابر است با

\sum_{i=1}^n \hat c_i = \sum_{i=1}^n \left (c_i+\phi(D_i)-\phi (D_{i-1})\right) =\sum_{i=1}^n c_i+\phi(D_n)-\phi (D_0) 

اگر بتوانیم یک تابع پتانسیل \phi  تعریف کنیم بطوریکه \phi (D_n)>= \phi (D_0)  ، آنگاه هزینه سرشکن شده کل \sum_{i=1}^n \hat c_i  ، یک حد بالا برای هزینه واقعی کل \sum_{i=1}^n c_i   می‌باشد. در عمل همواره نمی‌دانیم چه تعداد عمل ممکن است انجام شود. بنابراین اگر برای تمام iها تأکید کنیم که\phi(D_n)>= \phi(D_0)، آنگاه همانند روش حسابداری تضمین می‌کنیم که از پیش هزینه را پرداخت کرده‌ایم. اغلب مناسب است که \phi (D_0)   را 0  تعریف کنیم و آنگاه نشان دهیم که برای تمام iها، \phi (D_i)>=0.
به‌طور شهودی اگر اختلاف پتانسیل \phi (D_i) - \phi (D_{i-1})   از i امین عمل مثبت باشد آنگاه هزینه سرشکن شده  \hat c_i   یک پرداخت اضافه به i امین عمل را نشان می‌دهد، و پتانسیل ساختمان داده افزایش می‌یابد. اگر اختلاف پتانسیل منفی باشد، آنگاه هزینه سرشکن شده، یک پرداخت کم به i امین عمل را نشان می‌دهد و هزینه واقعی عمل با کاهش پتانسیل پرداخت می‌شود.
هزینه‌های سر شکن شده تعریف شده به وسیله دو معادلهٔ بالا به انتخاب تابع پتانسیل \phi  بستگی دارد. توابع پتانسیل متفاوت ممکن است به هزینه‌های سرشکن شده متفاوت که همچنان حدود بالا برای هزینه‌های واقعی اند منجر گردند. اغلب در انتخاب یک تابع پتانسیل مبادلاتی می‌توانند انجام گیرند؛ بهترین تابع پتانسیل جهت استفاده بستگی به حدود زمانی مطلوب دارد.

## منابع
کتاب CLRS

## پانویس

رده:تحلیل الگوریتم‌ها
رده:ساختمان داده