آنالیز استهلاکی کیست؟ توضیح بده.
تحلیل سر‌شکن:در این نوع آنالیز، n عمل انجام می‌شود و هزینه زمانی آن روی n عمل سرشکن می‌شود. در واقع ممکن است عملیات انجام شده هزینه‌های مختلفی داشته باشند و برخی هزینه زیادی داشته باشند ولی هزینه متوسط هر عمل کوچک باشد. لازم به ذکر است که آنالیز استهلاکی با آنالیز در حالت میانگین متفاوت است و روش‌های آماری را شامل نمی‌شود. در واقع آنالیز استهلاکی زمان اجرای متوسط هر عمل در بدترین حالت را نشان می دهد.برای این نوع آنالیز 3 روش مطرح است:آنالیز تجمعیدر این روش هزینه n عمل را به دست می آوریم سپس به n تقسیم می کنیم . مثلاً n عمل formula_1 روی پشته s که در ابتدا خالی است انجام داده ایم formula_2 (عنصر از پشته pop می کند، البته اگر کمتر از k عنصر در پشته باشند، همه عناصر pop می شوند) درست است که هزینه formula_2 ممکن است formula_4 باشد ولی n عمل از عملیات فوق روی هم هزینه formula_5 باشد ولی N عمل از عملیات فوق روی هم هزینه formula_5 دارند پس هزینه هر عمل به صورت سرشکن شده برابر formula_7 است.روش حسابرسی در این روش به عملیات مختلف، شارژهای مختلفی نسبت می دهیم که ممکن است شارژی که نسبت می دهیم، از هزینه واقعی عمل کمتر یا بیشتر باشد . مقداری که یک عمل شارژ می‌شود را «هزینه استهلاک » آن عمل گویند.اگر « هزینه استهلاک » یک عمل از «هزینه واقعی » آن عمل بیشتر باشد، تفاوت این دو به عنوان «اعتبار» به عناصر خاصی از ساختمان داده تخصیص می یابد. این اعتبار را می توان بعداً برای عملیاتی که هزینه استهلاکشان کمتر از هزینه واقعی شان است، صرف کرد.به عنوان مثال عملیات پشته را در نظر بگیرید . می دانیم هزینه واقعی عملیات عبارت است از :formula_8 که s تعداد عناصر موجود در پشته هنگام فراخوانی Multipop است.ولی ما هزینه استهلاکی زیر را به عملیات نسبت می دهیم :formula_9 با این مقادیر، می توان هر دنباله از عملیات را پشتیبانی کرد. هر push که انجام می شود، هزینه واقعی اش 1 است، پس از شارژ 2 مقداری آن ، 1 مقدار برای هزینه اش صرف می‌شود و 1 مقدار در عنصر push شده به عنوان اعتبار ذخیره می شود، پس تمام عناصری که در پشته هستند، اعتبار 1 مقداری دارند. حال اگر pop انجام شود، چون هزینه واقعی pop ، 1 است، این 1 را از اعتبار عنصری که pop می شود، دریافت می کند . پس از آنجایی که هزینه استهلاکی push ، pop و Multipop ثابت formula_10 است پس هزینه Nعمل ، formula_5 است.روش پتانسیل روش قبلی، اعتبار را به عنصر تخصیص می داد ولی این روش، اعتبار را به صورت پتانسیل به کل ساختمان داده تخصیص می دهد.فرض کنیدformula_12 وضعیت اولیه ساختمان داده ای است که می خواهیم formula_13 عمل روی آن انجام دهیم. formula_14 هزینه واقعی عمل i ام ، formula_15 وضعیت ساختمان داده است پس از انجام عمل i ام روی formula_16 تابع پتانسیلی تعریف می کنیم به اسمformula_17 که به هر وضعیت ساختمان داده، یک عدد حقیقی نسبت می دهد: یک عدد حقیقی=formula_18 بنابراین هزینه استهلاکی formula_19 عمل i ام برابر است با : formula_20&lt;br&gt;پس کل هزینه استهلاکی برابر است با :formula_21مثلاً فرض کنید در عملیات پشته formula_1، تابع پتانسیل formula_17 را برابر عناصر موجود در پشته فرض کنیم . در حالت پشته خالی formula_12، که حالت شروع استformula_25. از آنجایی که تعداد عناصر موجود در پشته عددی نامنفی است پس همیشه formula_26 . پس هزینه کل مستهلک شده برای formula_13 عمل با توجه به تابع formula_17، یک کران بالا برای هزینه واقعی است. حال هزینه مستهلک شده را برای formula_1 به دست می آوریم . اگر عمل formula_30ام روی پشته formula_31 باشد و در حال حاضر تعداد formula_32 عنصر در پشته باشد آنگاه:formula_33بنابراین هزینه مستهلک شده formula_31 برابر است با :formula_35به همین ترتیب نشان دهید که هزینه مستهلک شده formula_36 برابر صفر است. پس هزینه مستهلک شده هر عمل formula_7 است. بنابراین از آنجایی که هزینه مستهلک شده کران بالای هزینه واقعی است پس هزینه واقعی formula_13 عمل برابر formula_5 است.منابع.کتاب طراحی الگوریتم- هادی یوسفی