ⓘ تابع پتانسیل در تحلیل سرشکن. روش تابع پتانسیل در تحلیل سرشکن ، روشی است که در تحلیل و محاسبه پیچیدگی زمانی یک ساختمان داده در علوم رایانه به کار می رود برای درک ..

                                     

ⓘ تابع پتانسیل در تحلیل سرشکن

روش تابع پتانسیل در تحلیل سرشکن ، روشی است که در تحلیل و محاسبه پیچیدگی زمانی یک ساختمان داده در علوم رایانه به کار می رود برای درک بهتر منظور، بهتر است ابتدا با تحلیل سرشکن و روش های آن آشنا شوید.

                                     

1. تحلیل سرشکنی

احتمالاً با تحلیل الگوریتم ها در بدترین حالت و حالت میانگین در علوم کامپیوتر آشنا هستید. بعضی عواملی وجود دارند که سبب می شوند ما از تحلیل سرشکن شده استفاده کنیم. در واقع تحلیل سرشکن شده بدین منظور است که هر عملیات یک هزینه ی واقعی دارد و یک هزینه ی سرشکن شده.

برخی از اعمال انجام شده روی داده ساختارها به طوری است که برای یکی دو مورد از ورودی ها هزینه ی انجام عمل بسیار بالا ولی دربیشتر موارد هزینه به نسبت کمتری دارد.

گاهی نیز مواردی وجود دارد که در آن هزینه ی اعمال کم است اما تعداد آنها بسیار زیاد است.

همچنین شرایطی است که انجام یک عمل با هزینه ی زیاد نیاز است، زیرا باعث میشود هزینه ی اعمال بعدی بسیار کمتر شود. در تمام شرایط ذکر شده هزینه ی انجام عمل در بدترین حالت بسیار زیاد میشود اما اگر هزینه را در حالت میانگین به دست آوریم هزینه ی نسبتاً بهتری خواهیم داشت که به این "هزینه ی سرشکن شده" می گویند.

                                     

2. تابع پتانسیل

روش تابع پتانسیل در واقع قوی ترین روش اثبات در تحلیل سرشکن می باشد، اما دقت کنید که پیدا کردن تابع پتانسیل به هیچ عنوان ساده هم نیست. تابع پتانسیلی که برای اثبات مرتبه ی زمانی مجموعه های مجزا مطرح شده است به ما نشان می دهد به تعریف کردن تابع پتانسیل آسان هم نیست.

دقت کنید که با تمام روش های تحلیل سرشکنی از نظر اردری به جواب یکسانی خواهیم رسید اما روش تابع پتانسیل قطعی و دقیق تر از همه روش های تحلیل زمان سرشکن می باشد

روش تابع پتانسیل حالت جامع تری از روش حساب داری می باشد. این روش در واقع همان بیان ریاضی روش حساب داری برای تحلیل سرشکنی می باشد اما در حالت کلی تری از آن است.

فرض کنید D 0 {\displaystyle D_{0}} داده ساختار اولیه و D i {\displaystyle D_{i}} داده ساختار بعد از اعمال عمل i ام باشد یا به بیان دیگر:

خب حال c i {\displaystyle c_{i}} را هزینه ی واقعی i امین عمل در نظر بگیرید.

در این صورت ϕ D i {\displaystyle \phi D_{i}} را تابعی تعریف میکنیم که D i {\displaystyle D_{i}} را به یک عدد حقیقی نا منفی نگاشت میکند.

همچنین c ^ {\displaystyle {\hat {c}}} راتعریف می کنیم:

و آن را هزینه ی سرشکن شده ی عملi ام می نامیم. اگر ϕ D 0 = 0 {\displaystyle \phi D_{0}=0} داریم

یعنی ∑ i = 1 n c i ^ {\displaystyle \sum _{i=1}^{n}{\hat {c_{i}}}} کران بالایی برای ∑ i = 1 n c i {\displaystyle \sum _{i=1}^{n}c_{i}} است که میخواهیم به دست بیاوریم.

                                     

3. مثال

push

در این حالت چون یک عنصر را اضافه می کنیم تابع را به صورت رو به رو تعریف می کنیم:

و از طرفی میدانیم که هر درج به اندازه ی یک واحد هزینه دارد یعنی c i = 1 {\displaystyle c_{i}=1}

pop

در این حالت چون یک عنصر کم میشود:

هزینه ی حذف هم که مانند درج 1 است لذا c i ^ = 1 − 1 = 0 {\displaystyle {\hat {c_{i}}}=1-1=0}

                                     

3.1. مثال تحلیل پشته به روش پتانسیل

یک نمونه از کاربرد های روش پتانسیل در بحث ساختمان داده ها تحلیل زمانی پشته ها می باشد.

دراین روش ϕ D i {\displaystyle \phi D_{i}} را برابر تعداد عناصر موجود در پشته در نظر گرفته و بدیهی است که در ابتدا ϕ D 0 = 0 {\displaystyle \phi D_{0}=0} و همیشه مقدارش مثبت است، لذا ϕ {\displaystyle \phi } یک تابع پتانسیل است. حال برای دو دستور Push و Pop که در استفاده از پشته ها بسیار پر کاربرد می باشند، هزینه ی سرشکن شده را بدست می آوریم:

                                     

3.2. مثال push

در این حالت چون یک عنصر را اضافه می کنیم تابع را به صورت رو به رو تعریف می کنیم:

و از طرفی میدانیم که هر درج به اندازه ی یک واحد هزینه دارد یعنی c i = 1 {\displaystyle c_{i}=1}

                                     

3.3. مثال تحلیل شمارشگر دودویی

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

می خواهیم نشان دهیم که اضافه کردن 1 یعنی عملیات دوم در واقع 1 O زمان سرشکن دارد.

برای تحلیل این منظور از روش تابع پتانسیل استفاده می کنیم، بدین صورت که:

تایع ϕ D i {\displaystyle \phi D_{i}} را تابعی برابر با تعداد یک ها قرار می دهیم. قابل توجه است که این تابع همواره نا منفی است.

با عملیات انجام شده همواره کمترین مقدار LSB تغیر می کند بدین صورت که اگر این کم ترین مقدار از 1 به صفر تغییر کند، بیت بعدی نیز تغیر می کند و این روند ادامه می یابد تا اینکه در نهایت از 0 به 1 تغیر کنیم که در این مرحله فلیپ متوقف می شود.

اگر شمارنده در ابتدا با K تا بیت 1 ختم شود، در کل بیت های K+1 می گیریم. زمان واقعی K +1 و پتانسیل را با k-1 کاهش میدهیم، بنابر این زمان سرشکن برابر 2 است که ثابت کردیم این زمان در اردر 1 است: 1 O.

                                     

4. کاربرد

مجموعه های مجزا، آرایه های پویا، پشته های فیبوناچی و خیلی داده ساختار های دیگر با این روش تحلیل می شوند.

یکی دیگر از کاربرد های مهم روش تابع پتانسیل، حل کردن پیچیدگی زمانی شمارنده دودویی binary counter می باشد و با این روش میتوان ثابت کرد هزینه ی سرشکن هر بار شمارش در اردر یک است.

                                     
  • داده ذخیره می شود روش پتانسیل از تحلیل سرشکن شده کار از پیش پرداخته شده را به صورت انرژی پتانسیل یا تنها پتانسیل نمایش می دهد که می تواند جهت پرداخت
  • تقسیم شده است. این روش با تحلیل جمعی که در آن تمام اعمال هزینه های سرشکن شده یکسانی دارند بسیار متفاوت است. هزینه های سرشکن شده اعمال باید به دقت انتخاب
  • ضریب ثابت به نام ثابت مخفی مرتبط است. در مورد تحلیل الگوریتم باید در مورد موضوعاتی مانند تابع رشد روش تحلیل الگوریتم های ترتیبی و بازگشتی حل رابطه های
  • زمان اضافه در انتها از زمان اعمال کند کم می شود. این زمان ذخیره شده را می توان در هر زمانی با استفاده از تابع پتانسیل محاسبه نمود. پتانسیل هیپ فیبوناتچی
  • تحلیل سر شکن در این نوع آنالیز n عمل انجام می شود و هزینه زمانی آن روی n عمل سرشکن می شود. در واقع ممکن است عملیات انجام شده هزینه های مختلفی داشته