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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

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

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

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

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

منابع[ویرایش]

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

پیوند به بیرون[ویرایش]