آنالیز استهلاکی الگوریتم ها

آنالیز استهلاکی الگوریتم ها

در Amortized Analysis آنالیز استهلاکی برای تخمین زمان اجرای الگوریتم و پیچیدگی زمانی آن، n عمل انجام میشود و هزینه زمانی آن روی n عمل سرشکن میشود. در واقع ممکن است عملیات انجام شده هزینه های مختلفی داشته باشند و برخی هزینه زیادی داشته باشند ولی هزینه متوسط هر عمل کوچک باشد. لازم به ذکر است که آنالیز استهلاکی با آنالیز در حالت میانگین متفاوت است و روش های آماری را شامل نمیشود. در واقع آنالیز استهلاکی زمان اجرای متوسط هر عمل در بدترین حالت را نشان میدهد.

برای این نوع آنالیز 3 روش مطرح است:

► آنالیز تجمعی Aggregate Analysis

► روش حسابرسی Accounting method

► روش پتانسیل Potential Method

♦ آنالیز تجمعی

در این روش هزینه n عمل را به دست می آوریم سپس به n تقسیم میکنیم. مثلا n عمل push، pop و Multipop(k) روی پشته s که در ابتدا خالی است انجام داده ایم (Multipop(k) ، k عنصر از پشته pop میکند. البته اگر از k عنصر در پشته باشند، همه عناصر pop میشوند) درست است که هزینه Multipop(k) ممکن است O(k) باشد ولی n عمل از عملیات فوق روه هم هزینه O(n) دارند پس هزینه هر عمل بصورت سرشکن شده برابر O(1) است.

♦ روش حسابرسی

در این روش به عملیات مختلف، شارژهای مختلفی نسبت میدهیم که ممکن است شارژی که نسبت میدهیم، از هزینه واقعی عمل کمتر یا بیشتر باشد. مقداری که یک عمل شارژ میشود را "هزینه استهلاک" آن عمل گویند.

اگر "هزینه استهلاک" یک عمل از هزینه واقعی آن عمل بیشتر باشد، تفاوت این دو بعنوان "اعتبار"  به عناصر خاصی از ساختمان داده تخصیص می یابد. این اعتبار را میتوان بعدا برای عملیاتی که هزینه استهلاکشان کمتر از هزینه واقعی شان است، صرف کرد.

♦ روش پتانسیل

روش قبلی، اعتبار را به عنصر تخصیص میداد ولی این روش ، اعتبار را به صورت پتانسیل به کل ساختمان داده تخصیص میدهد.

فرض کنید D₀ وضعیت اولیه ساختمان داده ای است که میخواهیم n عمل روی آن انجام دهیم. C_i هزینه واقعی عمل i ام، D_i وضعیت ساختمان داده است پس از انجام عمل i  ام روی D_i-1 ، تابع پتانسیلی تعریف میکنیم به اسم ф که به هر وضعیت ساختمان داده، یک عدد حقیقی نسبت میدهد:

ф(D_i)  یک عدد حقیقی =

بنابراین هزینه استهلاکی عمل i ام برابر است با :

C’_i = C_i + ф(D_i) - ф(D_i-1)