موضوع مقاله: تابع پتانسیل در تحلیل سرشکن | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # تابع پتانسیل در تحلیل سرشکن | مقدمه: روش تابع پتانسیل در تحلیل سرشکن ، روشی است که در تحلیل و محاسبه پیچیدگی زمانی یک ساختمان داده در علوم رایانه به کار می رود برای درک بهتر منظور، بهتر است ابتدا با تحلیل سرشکن و روش های آن آشنا شوید. | ## بخش 1: تابع پتانسیل در تحلیل سرشکن | تحلیل سرشکنی احتمالاً با تحلیل الگوریتم ها در بدترین حالت و حالت میانگین در علوم کامپیوتر آشنا هستید. در واقع تحلیل سرشکن شده بدین منظور است که هر عملیات یک هزینه ی واقعی دارد و یک هزینه ی سرشکن شده. برخی از اعمال انجام شده روی داده ساختارها به طوری است که برای یکی دو مورد از ورودی ها هزینه ی انجام عمل بسیار بالا ولی دربیشتر موارد هزینه به نسبت کمتری دارد. گاهی نیز مواردی وجود دارد که در آن هزینه ی اعمال کم است اما تعداد آنها بسیار زیاد است. همچنین شرایطی است که انجام یک عمل با هزینه ی زیاد نیاز است، زیرا باعث میشود هزینه ی اعمال بعدی بسیار کمتر شود. در تمام شرایط ذکر شده هزینه ی انجام عمل در بدترین حالت بسیار زیاد میشود اما اگر هزینه را در حالت میانگین به دست آوریم هزینه ی نسبتاً بهتری خواهیم داشت که به این "هزینه ی سرشکن شده" می گویند. روش انبوهه روش حساب داری روش شارژ کردن روش تابع پتانسیل تابع پتانسیل روش تابع پتانسیل در واقع قوی ترین روش اثبات در تحلیل سرشکن می باشد، اما دقت کنید که پیدا کردن تابع پتانسیل به هیچ عنوان ساده هم نیست. | ## بخش 2: تابع پتانسیل در تحلیل سرشکن | تابع پتانسیلی که برای اثبات مرتبه ی زمانی مجموعه های مجزا مطرح شده است به ما نشان می دهد به تعریف کردن تابع پتانسیل آسان هم نیست. دقت کنید که با تمام روش های تحلیل سرشکنی از نظر اردری به جواب یکسانی خواهیم رسید اما روش تابع پتانسیل قطعی و دقیق تر از همه روش های تحلیل زمان سرشکن می باشد روش تابع پتانسیل حالت جامع تری از روش حساب داری می باشد . این روش در واقع همان بیان ریاضی روش حساب داری برای تحلیل سرشکنی می باشد اما در حالت کلی تری از آن است. فرض کنید داده ساختار اولیه و داده ساختار بعد از اعمال عمل i ام باشد یا به بیان دیگر: خب حال را هزینه ی واقعی i امین عمل در نظر بگیرید. تحلیل آرایه پویا تحلیل پشته به روش پتانسیل یک نمونه از کاربرد های روش پتانسیل در بحث ساختمان داده ها تحلیل زمانی پشته ها می باشد. دراین روش را برابر تعداد عناصر موجود در پشته در نظر گرفته و بدیهی است که در ابتدا و همیشه مقدارش مثبت است، لذا یک تابع پتانسیل است. حال برای دو دستور Push و Pop که در استفاده از پشته ها بسیار پر کاربرد می باشند، هزینه ی سرشکن شده را بدست می آوریم: push در این حالت چون یک عنصر را اضافه می کنیم تابع را به صورت رو به رو تعریف می کنیم : و از طرفی میدانیم که هر درج به اندازه ی یک واحد هزینه دارد یعنی pop در این حالت چون یک عنصر کم میشود : هزینه ی حذف هم که مانند درج 1 است لذا تحلیل شمارشگر دودویی در واقع شمارنده ایی که روی آن قرار است کار کنیم را یک عدد دودویی در نظر بگیرید به صورتی که عملیات های مقدار دهی اولیه، اضافه کردن 1 و خواندن از روی شمارنده را انجام دهد. | ## بخش 3: تابع پتانسیل در تحلیل سرشکن | می خواهیم نشان دهیم که اضافه کردن 1 یعنی عملیات دوم در واقع (1) O زمان سرشکن دارد. برای تحلیل این منظور از روش تابع پتانسیل استفاده می کنیم، بدین صورت که: تایع را تابعی برابر با تعداد یک ها قرار می دهیم. با عملیات انجام شده همواره کمترین مقدار (LSB) تغیر می کند بدین صورت که اگر این کم ترین مقدار از 1 به صفر تغییر کند، بیت بعدی نیز تغیر می کند و این روند ادامه می یابد تا اینکه در نهایت از 0 به 1 تغیر کنیم که در این مرحله فلیپ متوقف می شود. زمان واقعی K +1 و پتانسیل را با k-1 کاهش میدهیم، بنابر این زمان سرشکن برابر 2 است که ثابت کردیم این زمان در اردر 1 است: (1) O. کاربرد مجموعه های مجزا، آرایه های پویا، پشته های فیبوناچی و خیلی داده ساختار های دیگر با این روش تحلیل می شوند. | ## جمع‌بندی | یکی دیگر از کاربرد های مهم روش تابع پتانسیل، حل کردن پیچیدگی زمانی شمارنده دودویی (binary counter) می باشد و با این روش میتوان ثابت کرد هزینه ی سرشکن هر بار شمارش در اردر یک است.