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

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

تحلیل جمعی

در تحلیل جمعی[2] نشان می‌دهیم که به ازای تمام ${\displaystyle n}$ها، یک توالی از ${\displaystyle n}$ عمل در مجموع، زمان ${\displaystyle T(n)}$ را در بدترین حالت صرف می‌کند. بنابراین در بدترین حالت، هزینه میانگین، یا هزینه سرشکن شده [1] برای هر عمل برابر${\displaystyle T(n)/n}$ است. این هزینه سرشکن شده برای هر عمل به کار می‌رود، حتی وقتی که چندین نوع عمل در توالی وجود داشته باشند. دو روش دیگر، روش حسابداری و روش پتانسیل، ممکن است هزینه‌های سرشکن شده متفاوتی به انواع متفاوت عمل‌ها نسبت دهند.

روش حسابداری

در روش حسابداری [3] از تحلیل سرشکن شده، به عمل‌های متفاوت هزینه‌های متفاوتی اختصاص می‌دهیم، به طوری که به تعدادی از اعمال هزینه بیشتر و به تعدادی هزینه کمتری نسبت به هزینه واقعی آن‌ها اختصاص داده می‌شود. مقدار هزینه‌ای که به یک عمل می‌دهیم، هزینه سرشکن شده آن عمل نامیده می‌شود. هنگامی که هزینه سرشکن شده یک عمل از هزینه واقعی آن تجاوز کند، اختلاف هزینه به عنوان موجودی به اشیایی مشخص در ساختمان داده اختصاص می‌یابد. موجودی بعداً می‌تواند در جهت کمک به پرداخت برای اعمالی که هزینه سرشکن شده آنها کمتر از هزینه واقعی شان است مورد استفاده قرار گیرد. بنابراین می‌توان هزینه سرشکن شده یک عمل را مشاهده کرد که بین هزینه واقعی آن و موجودی که پرداخت شده یا استفاده می‌شود، تقسیم شده‌است. این روش با تحلیل جمعی که در آن تمام اعمال هزینه‌های سرشکن شده یکسانی دارند، بسیار متفاوت است. هزینه‌های سرشکن شده اعمال باید به دقت انتخاب شوند. اگر بخواهیم تحلیل را با هزینه‌های سرشکن شده انجام دهیم تا نشان دهیم که در بدترین حالت هزینه میانگین هر عمل کم است، کل هزینه سرشکن شده یک توالی از اعمال باید یک حد بالا برای هزینه کل واقعی توالی باشد. علاوه بر این همانند تحلیل جمعی، این رابطه باید برای تمام توالی‌های اعمال برقرار باشد. اگر هزینه واقعی ${\displaystyle i}$ امین عمل را با ${\displaystyle c_{i}}$ و هزینه سرشکن شده ${\displaystyle i}$ امین عمل را با ${\displaystyle {\hat {c}}_{i}}$ نشان دهیم، برای تمام توالی‌هایی از ${\displaystyle n}$ عمل نیاز داریم

${\displaystyle \sum _{i=1}^{n}{\hat {c}}_{i}>=\sum _{i=1}^{n}c_{i}}$

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

روش پتانسیل

به جای نمایش کار از پیش پرداخت شده به صورت موجودی، که با اشیایی مشخص در ساختمان داده ذخیره می‌شود، روش پتانسیل [4] از تحلیل سرشکن شده، کار از پیش پرداخته شده را به صورت “انرژی پتانسیل” یا تنها “پتانسیل” نمایش می‌دهد که می‌تواند جهت پرداخت برای اعمال آینده آزاد شود. پتانسیل به جای آنکه به اشیای خاص در داخل ساختمان داده اختصاص داده شود، به کل ساختمان داده اختصاص داده می‌شود. روش پتانسیل به صورت زیر کار می‌کند. با یک ساختمان داده اولیه ${\displaystyle D_{0}}$ را شروع می‌کنیم که روی آن ${\displaystyle n}$ عمل انجام می‌شود. برای هر ${\displaystyle i=1,2,\cdots ,n}$، ${\displaystyle c_{i}}$ را هزینه واقعی ${\displaystyle i}$ امین عمل قرار می‌دهیم و ${\displaystyle D_{i}}$ را ساختمان داده‌ای که پس از به کارگیری ${\displaystyle i}$ امین عمل روی ساختمان داده ${\displaystyle D_{i-1}}$ حاصل می‌شود، قرار می‌دهیم. تابع پتانسیل[5]${\displaystyle \phi }$ هر ساختمان داده ${\displaystyle D_{i}}$ را به یک عدد حقیقی ${\displaystyle \phi (D_{i})}$ نگاشت می‌کند. این عدد، پتانسیل [6] مربوط به ساختمان دادهٔ ${\displaystyle D_{i}}$ است. هزینه سر شکن شده ${\displaystyle {\hat {c}}_{i}}$ مربوط به ${\displaystyle i}$ امین عمل با توجه به تابع پتانسیل ${\displaystyle \phi }$ به صورت زیر تعریف می‌شود

${\displaystyle {\hat {c}}_{i}=c_{i}+\phi (D_{i})-\phi (D_{i-1})}$

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

${\displaystyle \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})}$

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

منابع

کتاب CLRS

پانویس

1. amortized analysis
2. aggregate analysis
3. accounting method
4. potential method
5. potential function
6. potential