آنالیز استهلاکی

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

1. آنالیز تجمعی (Aggregate Analysis)
2. روش حسابرسی (Accounting Method)
3. روش پتانسیل (Potential Method)

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

روش حسابرسی
در این روش به عملیات مختلف، شارژهای مختلفی نسبت می دهیم که ممکن است شارژی که نسبت می دهیم، از هزینه واقعی عمل کمتر یا بیشتر باشد . مقداری که یک عمل شارژ می‌شود را «هزینه استهلاک » آن عمل گویند. اگر « هزینه استهلاک » یک عمل از «هزینه واقعی » آن عمل بیشتر باشد، تفاوت این دو به عنوان «اعتبار» به عناصر خاصی از ساختمان داده تخصیص می یابد. این اعتبار را می توان بعداً برای عملیاتی که هزینه استهلاکشان کمتر از هزینه واقعی شان است، صرف کرد.
به عنوان مثال عملیات پشته را در نظر بگیرید . می دانیم هزینه واقعی عملیات عبارت است از :
${\displaystyle Push=1,pop=1,Multipop(k)=min(k,s)}$
که s تعداد عناصر موجود در پشته هنگام فراخوانی Multipop است.
ولی ما هزینه استهلاکی زیر را به عملیات نسبت می دهیم :
${\displaystyle Push2,pop0,Multipop0}$
با این مقادیر، می توان هر دنباله از عملیات را پشتیبانی کرد. هر push که انجام می شود، هزینه واقعی اش 1 است، پس از شارژ 2 مقداری آن ، 1 مقدار برای هزینه اش صرف می‌شود و 1 مقدار در عنصر push شده به عنوان اعتبار ذخیره می شود، پس تمام عناصری که در پشته هستند، اعتبار 1 مقداری دارند. حال اگر pop انجام شود، چون هزینه واقعی pop ، 1 است، این 1 را از اعتبار عنصری که pop می شود، دریافت می کند . پس از آنجایی که هزینه استهلاکی push ، pop و Multipop ثابت ${\displaystyle (O(1))}$ است پس هزینه Nعمل ، ${\displaystyle O(n)}$ است.

روش پتانسیل
روش قبلی، اعتبار را به عنصر تخصیص می داد ولی این روش، اعتبار را به صورت پتانسیل به کل ساختمان داده تخصیص می دهد. فرض کنید${\displaystyle D_{0}}$ وضعیت اولیه ساختمان داده ای است که می خواهیم ${\displaystyle n}$ عمل روی آن انجام دهیم. ${\displaystyle C_{i}}$ هزینه واقعی عمل i ام ، ${\displaystyle D_{i}}$ وضعیت ساختمان داده است پس از انجام عمل i ام روی ${\displaystyle D_{(}i-1)}$ تابع پتانسیلی تعریف می کنیم به اسم${\displaystyle \propto }$ که به هر وضعیت ساختمان داده، یک عدد حقیقی نسبت می دهد:
یک عدد حقیقی=${\displaystyle \propto (D_{i})}$
بنابراین هزینه استهلاکی ${\displaystyle {\check {C_{i}}}}$ عمل i ام برابر است با : ${\displaystyle {\check {C_{i}}}=C_{i}+\propto (D_{i})-\propto (D_{i-1})}$
پس کل هزینه استهلاکی برابر است با : ${\displaystyle \sum _{i=1}^{n}C_{i}+\propto (D_{i})-\propto (D_{i-1})}$
مثلاً فرض کنید در عملیات پشته ${\displaystyle Multipop(k),pop,push}$، تابع پتانسیل ${\displaystyle \propto }$ را برابر عناصر موجود در پشته فرض کنیم . در حالت پشته خالی ${\displaystyle D_{0}}$، که حالت شروع است${\displaystyle \propto (D_{0})=0}$. از آنجایی که تعداد عناصر موجود در پشته عددی نامنفی است پس همیشه ${\displaystyle \propto (D_{i})>=0=\propto (D_{0})}$ . پس هزینه کل مستهلک شده برای ${\displaystyle n}$ عمل با توجه به تابع ${\displaystyle \propto }$، یک کران بالا برای هزینه واقعی است. حال هزینه مستهلک شده را برای ${\displaystyle Multipop(k),pop,push}$ به دست می آوریم .
اگر عمل ${\displaystyle i}$ام روی پشته ${\displaystyle push}$ باشد و در حال حاضر تعداد ${\displaystyle s}$ عنصر در پشته باشد آنگاه:
${\displaystyle \propto (D_{i})-\propto (D_{i-1})=(s+1)-s}$
بنابراین هزینه مستهلک شده ${\displaystyle push}$ برابر است با :
${\displaystyle {\check {c_{i}}}+\propto (D_{i})-\propto (D_{i-1})=1+1=2}$
به همین ترتیب نشان دهید که هزینه مستهلک شده ${\displaystyle Multipop,pop}$ برابر صفر است. پس هزینه مستهلک شده هر عمل ${\displaystyle O(1)}$ است . بنابراین از آنجایی که هزینه مستهلک شده کران بالای هزینه واقعی است پس هزینه واقعی ${\displaystyle n}$ عمل برابر ${\displaystyle O(n)}$ است.

منابع

کتاب طراحی الگوریتم- هادی یوسفی

پیوند به بیرون

• آنالیز استهلاکی, تدریس چارلز.ای لیزرسان- ام آی تی
• آنالیز استهلاکی, کتاب مقدمه ای بر الگوریتمها