روش پتانسیل

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

تحلیل امورتایز برای بدترین ورودی‌ها

معمولاً، تحلیل امورتایز با فرض بدترین حالت برای ورودی ترکیب می‌شود. با این فرض، اگر X یک نوع عملگر است که توسط ساختمان داده اجرا می‌شود و n عددی صحیح است که سایز ساختمان داده را مشخص می‌کند، (برای نمونه، تعداد داده‌هایی که شامل می‌شود) زمان امورتایز برای عملگرهایی از نوع X، در بین تمامی مجموعه عملگرهای ممکن بر روی ساختمان داده ای با اندازهٔ n و همهٔ عملگرهای oᵢ از نوع X در مجموعه به صورت ماکسیمم زمان امورتایز برای عملگر oᵢ تعریف می‌شود.
با این تعریف، زمان اجرای یک مجموعه از عملگرها به صورت ضرب زمان امورتایر برای هر نوع عملگر داخل مجموعه در تعداد عملگرهایی از آن نوع تخمین زده می‌شود.

مثال

یک آرایهٔ داینامیک، ساختمان داده ای برای نگهداری یک آرایه از اشیا است، که هم دسترسی رندم به مکان‌های آرایه و همچنین توانایی افزایش طول آرایه به اندازهٔ یک واحد را فراهم می‌کند. این ساختمان داده در جاوا به صورت "ArrayList" و در Python به صورت "List" فراهم است.
یک آرایهٔ داینامیک می‌تواند به صورت یک ساختمان داده شامل یک آرایهٔ A از اشیا به طول N، و یک عدد n نشان دهندهٔ مکان‌هایی از آرایه است که تا به حال استفاده شده‌اند. با این ساختمان داده، دسترسی رندم به آرایه داینامیک با دسترسی به همان مکان آرایه داخلی A امکان‌پذیر است و زمانی که n < N یک عملگر که طول آرایه داینامیک را افزایش می‌دهد به سادگی با افزایش n امکان‌پذیر است. به هر حال وقتی n = N باید اندازهٔ آرایهٔ A بزرگتر شود و یک استراتژی معمول برای انجام این کار دو برابر کردن اندازهٔ A است (جایگزین کردن A با یک آرایه به طول 2n)
این ساختار می‌تواند با تابع پتانسیل Φ = 2n − N تحلیل شود.
از آنجایی که استراتژی تغییر اندازه همیشه باعث می‌شود آرایه A حداقل نیمه پر باشد، این تابع پتانسیل همواره نامنفی است، همان‌طور که مطلوب است. هنگامی که عمل افزایش طول به تغییر طول آرایه نمی‌انجامد، Φ به اندازهٔ یک ثابت ۲ افزایش می‌یابد؛ بنابراین زمان ثابت واقعی عمل و افزایش مقدار ثابت پتانسیل ترکیب می‌شوند تا زمان امورتایز ثابتی ازین نوع بدهند.
به هر حال، وقتی افزایش اندازه به تغییر سایز می‌انجامد، مقدار پتانسیل قبل از تغییر سایز، بعد تغییر سایز به صفر کاهش می‌یابد. به وجود آوردن یک آرایه درونی جدید A و کپی کردن تمام اعضای آرایهٔ قبلی در آرایه جدید زمان واقعی (Φ(n را هزینه می‌کند، اما (با انتخاب مناسب ثابت تناسب C) این هزینه به‌طور کامل با کاهش n در تابع پتانسیل از بین می‌رود و دوباره یک زمان امورتایز ثابت برای عمل به جا می‌گذارد.
اعمال دیگر ساختمان داده (خواندن و نوشتن اعضای حافظه بدون تغییر اندازه) با عث تغییر تابع پتانسیل نمی‌شوند و زمان امورتایز مشابهی با زمان واقعی عمل دارند؛ بنابراین با انتخاب این استراتژی تغییر اندازه و تابع پتانسیل، روش پتانسیل نشان می‌دهد که همهٔ اعمال آرایهٔ داینامیک زمان امورتایز ثابت می‌گیرند. ترکیب این مطلب و نامساوی زمان امورتایز و زمان واقعی در یک مجموعه از اعمال، نشان می‌دهد که هر مجموعه از n عمل بر روی آرایه داینامیک زمان واقعی (Φ(n را در بدترین حالت می‌گیرد، با وجود این که هر عمل مستقل می‌تواند می‌تواند زمان خطی را هزینه کند

کاربردها

تابع پتانسل معمولاً برای تحلیل پشته‌های فیبو ناچی، یک نوع صف اولویت که حذف یک شی زمان امورتایز لگاریتمی و بقیه اعمال زمان امورتایز ثابت می‌گیرند. همچنین ممکن است در تحلیل درخت‌های اسپلی، یک درخت دودویی جستجو که خودکار تنظیم می‌شود و زمان امورتایز لگاریتمی در هر عمل می‌گیرد.