تابع پتانسیل در تحلیل سرشکن
روش تابع پتانسیل در تحلیل سرشکن ، روشی است که در تحلیل و محاسبه پیچیدگی زمانی یک ساختمان داده در علوم رایانه به کار می رود برای درک بهتر منظور، بهتر است ابتدا با تحلیل سرشکن و روش های آن آشنا شوید.
احتمالاً با تحلیل الگوریتم ها در بدترین حالت و حالت میانگین در علوم کامپیوتر آشنا هستید. بعضی عواملی وجود دارند که سبب می شوند ما از تحلیل سرشکن شده استفاده کنیم. در واقع تحلیل سرشکن شده بدین منظور است که هر عملیات یک هزینه ی واقعی دارد و یک هزینه ی سرشکن شده.
برخی از اعمال انجام شده روی داده ساختارها به طوری است که برای یکی دو مورد از ورودی ها هزینه ی انجام عمل بسیار بالا ولی دربیشتر موارد هزینه به نسبت کمتری دارد.
گاهی نیز مواردی وجود دارد که در آن هزینه ی اعمال کم است اما تعداد آنها بسیار زیاد است.
همچنین شرایطی است که انجام یک عمل با هزینه ی زیاد نیاز است، زیرا باعث میشود هزینه ی اعمال بعدی بسیار کمتر شود. در تمام شرایط ذکر شده هزینه ی انجام عمل در بدترین حالت بسیار زیاد میشود اما اگر هزینه را در حالت میانگین به دست آوریم هزینه ی نسبتاً بهتری خواهیم داشت که به این "هزینه ی سرشکن شده" می گویند.
به روش میشود تحلیل سرشکنی انجام میشود.
روش تابع پتانسیل در واقع قوی ترین روش اثبات در تحلیل سرشکن می باشد، اما دقت کنید که پیدا کردن تابع پتانسیل به هیچ عنوان ساده هم نیست. تابع پتانسیلی که برای اثبات مرتبه ی زمانی مجموعه های مجزا مطرح شده است به ما نشان می دهد به تعریف کردن تابع پتانسیل آسان هم نیست.
دقت کنید که با تمام روش های تحلیل سرشکنی از نظر اردری به جواب یکسانی خواهیم رسید اما روش تابع پتانسیل قطعی و دقیق تر از همه روش های تحلیل زمان سرشکن می باشد
روش تابع پتانسیل حالت جامع تری از روش حساب داری می باشد . این روش در واقع همان بیان ریاضی روش حساب داری برای تحلیل سرشکنی می باشد اما در حالت کلی تری از آن است.
فرض کنید formula_1 داده ساختار اولیه و formula_2 داده ساختار بعد از اعمال عمل i ام باشد یا به بیان دیگر:
formula_3
خب حال formula_4 را هزینه ی واقعی i امین عمل در نظر بگیرید.
در این صورت formula_5 را تابعی تعریف میکنیم که formula_2 را به یک عدد حقیقی نا منفی نگاشت میکند.
همچنین formula_7 راتعریف می کنیم:
formula_8 و آن را هزینه ی سرشکن شده ی عملi ام می نامیم.
اگر formula_9داریم formula_10
یعنی formula_11 کران بالایی برای formula_12 است که میخواهیم به دست بیاوریم.
یک نمونه از کاربرد های روش پتانسیل در بحث ساختمان داده ها تحلیل زمانی پشته ها می باشد.
دراین روش formula_5 را برابر تعداد عناصر موجود در پشته در نظر گرفته و بدیهی است که در ابتدا formula_9 و همیشه مقدارش مثبت است، لذا formula_15 یک تابع پتانسیل است. حال برای دو دستور Push و Pop که در استفاده از پشته ها بسیار پر کاربرد می باشند، هزینه ی سرشکن شده را بدست می آوریم:
در این حالت چون یک عنصر را اضافه می کنیم تابع را به صورت رو به رو تعریف می کنیم : formula_16
formula_18
در این حالت چون یک عنصر کم میشود : formula_19
هزینه ی حذف هم که مانند درج 1 است لذا formula_20
در واقع شمارنده ایی که روی آن قرار است کار کنیم را یک عدد دودویی در نظر بگیرید به صورتی که عملیات های مقدار دهی اولیه، اضافه کردن 1 و خواندن از روی شمارنده را انجام دهد.
می خواهیم نشان دهیم که اضافه کردن 1 یعنی عملیات دوم در واقع (1) O زمان سرشکن دارد.
برای تحلیل این منظور از روش تابع پتانسیل استفاده می کنیم، بدین صورت که:
تایع formula_5 را تابعی برابر با تعداد یک ها قرار می دهیم. قابل توجه است که این تابع همواره نا منفی است.
با عملیات انجام شده همواره کمترین مقدار (LSB) تغیر می کند بدین صورت که اگر این کم ترین مقدار از 1 به صفر تغییر کند، بیت بعدی نیز تغیر می کند و این روند ادامه می یابد تا اینکه در نهایت از 0 به 1 تغیر کنیم که در این مرحله فلیپ متوقف می شود.
اگر شمارنده در ابتدا با K تا بیت 1 ختم شود، در کل بیت های K+1 می گیریم. زمان واقعی K +1 و پتانسیل را با k-1 کاهش میدهیم، بنابر این زمان سرشکن برابر 2 است که ثابت کردیم این زمان در اردر 1 است: (1) O.
مجموعه های مجزا، آرایه های پویا، پشته های فیبوناچی و خیلی داده ساختار های دیگر با این روش تحلیل می شوند.
یکی دیگر از کاربرد های مهم روش تابع پتانسیل، حل کردن پیچیدگی زمانی شمارنده دودویی (binary counter) می باشد و با این روش میتوان ثابت کرد هزینه ی سرشکن هر بار شمارش در اردر یک است.
کتاب طراحی و تحلیل الگوریتم ها نوشته دکتر محمد قدسی
CLRS