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

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

تحلیل سرشکنی

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

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

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

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

تفاوت درج عناصر مختلف در آرایه پویا

روش های تحلیل سرشکنی

به روش میشود تحلیل سرشکنی انجام میشود.

• روش انبوهه
• روش حساب داری
• روش شارژ کردن
• روش تابع پتانسیل

تابع پتانسیل

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

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

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

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

$D_{0}\to D_{1}\to ...\to D_{i}\to ...D_{n}$

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

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

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

$\sum _{i=1}^{n}{\hat {c_{i}}}=\sum _{i=1}^{n}c_{i}+\phi (D_{n})-\phi (D_{0})$

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

$\sum _{i=1}^{n}{\hat {c_{i}}}>=\sum _{i=1}^{n}c_{i}$

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

مثال

فرض کنید c هزینه ی هر بار درج باشد و N تعداد عناصری که میخواهیم در آرایه ی پویا درج کنیم در این صورت دو نمودار در واقع تفاوت هزینه ی سرشکن شده و هزینه ی واقعی را نشان می دهند.

تحلیل پشته به روش پتانسیل

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

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

push

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

$\phi (D_{i})-\phi (D_{i}-1)=1$

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

${\hat {c_{i}}}=c_{i}+\phi (D_{i})-\phi (D_{i}-1)=1+1=2$

pop

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

$\phi (D_{i})-\phi (D_{i}-1)=-1$

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

تحلیل شمارشگر دودویی

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

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

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

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

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

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

کاربرد

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

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

منابع

کتاب طراحی و تحلیل الگوریتم ها نوشته دکتر محمد قدسی

CLRS