روش تابع پتانسیل [ ۱] در تحلیل سرشکن ، روشی است که در تحلیل و محاسبه پیچیدگی زمانی یک ساختمان داده در علوم رایانه به کار می رود برای درک بهتر منظور، بهتر است ابتدا با تحلیل سرشکن[ ۲] و روش های آن آشنا شوید.
احتمالاً با تحلیل الگوریتم ها در بدترین حالت و حالت میانگین در علوم کامپیوتر آشنا هستید. بعضی عواملی وجود دارند که سبب می شوند ما از تحلیل سرشکن شده استفاده کنیم. در واقع تحلیل سرشکن شده بدین منظور است که هر عملیات یک هزینه ی واقعی دارد و یک هزینه ی سرشکن شده.
برخی از اعمال انجام شده روی داده ساختارها به طوری است که برای یکی دو مورد از ورودی ها هزینه ی انجام عمل بسیار بالا ولی دربیشتر موارد هزینه به نسبت کمتری دارد.
گاهی نیز مواردی وجود دارد که در آن هزینه ی اعمال کم است اما تعداد آنها بسیار زیاد است.
همچنین شرایطی است که انجام یک عمل با هزینه ی زیاد نیاز است، زیرا باعث میشود هزینه ی اعمال بعدی بسیار کمتر شود. در تمام شرایط ذکر شده هزینه ی انجام عمل در بدترین حالت بسیار زیاد میشود اما اگر هزینه را در حالت میانگین به دست آوریم هزینه ی نسبتاً بهتری خواهیم داشت که به این "هزینه ی سرشکن شده" می گویند.
به روش میشود تحلیل سرشکنی انجام میشود.
• روش انبوهه
• روش حساب داری
• روش شارژ کردن
• روش تابع پتانسیل
روش تابع پتانسیل در واقع قوی ترین روش اثبات در تحلیل سرشکن می باشد، اما دقت کنید که پیدا کردن تابع پتانسیل به هیچ عنوان ساده هم نیست. تابع پتانسیلی که برای اثبات مرتبه ی زمانی مجموعه های مجزا مطرح شده است به ما نشان می دهد به تعریف کردن تابع پتانسیل آسان هم نیست.
دقت کنید که با تمام روش های تحلیل سرشکنی از نظر اردری به جواب یکسانی خواهیم رسید اما روش تابع پتانسیل قطعی و دقیق تر از همه روش های تحلیل زمان سرشکن می باشد
روش تابع پتانسیل حالت جامع تری از روش حساب داری می باشد . این روش در واقع همان بیان ریاضی روش حساب داری برای تحلیل سرشکنی می باشد اما در حالت کلی تری از آن است.
فرض کنید D 0 داده ساختار اولیه و D i داده ساختار بعد از اعمال عمل i ام باشد یا به بیان دیگر:
D 0 → D 1 → . . . → D i → . . . D n
خب حال c i را هزینه ی واقعی i امین عمل در نظر بگیرید.
در این صورت ϕ ( D i ) را تابعی تعریف میکنیم که D i را به یک عدد حقیقی نا منفی نگاشت میکند.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفاحتمالاً با تحلیل الگوریتم ها در بدترین حالت و حالت میانگین در علوم کامپیوتر آشنا هستید. بعضی عواملی وجود دارند که سبب می شوند ما از تحلیل سرشکن شده استفاده کنیم. در واقع تحلیل سرشکن شده بدین منظور است که هر عملیات یک هزینه ی واقعی دارد و یک هزینه ی سرشکن شده.
برخی از اعمال انجام شده روی داده ساختارها به طوری است که برای یکی دو مورد از ورودی ها هزینه ی انجام عمل بسیار بالا ولی دربیشتر موارد هزینه به نسبت کمتری دارد.
گاهی نیز مواردی وجود دارد که در آن هزینه ی اعمال کم است اما تعداد آنها بسیار زیاد است.
همچنین شرایطی است که انجام یک عمل با هزینه ی زیاد نیاز است، زیرا باعث میشود هزینه ی اعمال بعدی بسیار کمتر شود. در تمام شرایط ذکر شده هزینه ی انجام عمل در بدترین حالت بسیار زیاد میشود اما اگر هزینه را در حالت میانگین به دست آوریم هزینه ی نسبتاً بهتری خواهیم داشت که به این "هزینه ی سرشکن شده" می گویند.
به روش میشود تحلیل سرشکنی انجام میشود.
• روش انبوهه
• روش حساب داری
• روش شارژ کردن
• روش تابع پتانسیل
روش تابع پتانسیل در واقع قوی ترین روش اثبات در تحلیل سرشکن می باشد، اما دقت کنید که پیدا کردن تابع پتانسیل به هیچ عنوان ساده هم نیست. تابع پتانسیلی که برای اثبات مرتبه ی زمانی مجموعه های مجزا مطرح شده است به ما نشان می دهد به تعریف کردن تابع پتانسیل آسان هم نیست.
دقت کنید که با تمام روش های تحلیل سرشکنی از نظر اردری به جواب یکسانی خواهیم رسید اما روش تابع پتانسیل قطعی و دقیق تر از همه روش های تحلیل زمان سرشکن می باشد
روش تابع پتانسیل حالت جامع تری از روش حساب داری می باشد . این روش در واقع همان بیان ریاضی روش حساب داری برای تحلیل سرشکنی می باشد اما در حالت کلی تری از آن است.
فرض کنید D 0 داده ساختار اولیه و D i داده ساختار بعد از اعمال عمل i ام باشد یا به بیان دیگر:
D 0 → D 1 → . . . → D i → . . . D n
خب حال c i را هزینه ی واقعی i امین عمل در نظر بگیرید.
در این صورت ϕ ( D i ) را تابعی تعریف میکنیم که D i را به یک عدد حقیقی نا منفی نگاشت میکند.
