روش پتانسیل

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

تعریف زمان امورتایزد

در روش پتانسیل، یک تابع Φ انتخاب می‌شود که حالات ساختمان داده را به اعداد نا منفی نسبت می‌دهد. اگر S یکی از حالت‌های ساختمان داده مورد نظر باشد، می‌توان به (Φ(S به عنوان مقدار انرژی پتانسیل ذخیره شده در آن حالت نگاه کرد؛ همچنین، می‌توان به آن به عنوان نشان دهندهٔ مقدار نامرتب بودن در حالت S یا فاصله از یک حالت ایده‌آل نگاه کرد. مقدار پتانسیل قبل از عمل مقدار دهی یک ساختمان داده صفر در نظر گرفته می‌شود. اگر o یک عملیات مستقل در یک سری عملیات بر روی ساختمان داده باشد و S_before نشان دهندهٔ حالت ساختمان داده قبل از عمل o و S_after نشان دهندهٔ حالت آن بعد از اتمام عمل o باشد زمان امورتایزد برای عمل o به صورت زیر تعریف می‌شود

$T_{\mathrm {amortized} }(o)=T_{\mathrm {actual} }(o)+C\cdot (\Phi (S_{\mathrm {after} })-\Phi (S_{\mathrm {before} }))$

که C یک ثابت تناسب غیر منفی است که در طول تحلیل باید ثابت بماند؛ بنابراین زمان امورتایز برابر است با زمان واقعی که عمل o هزینه کرده‌است بعلاوهٔ C برابر اختلاف پتانسیلی که توسط o ایجاد می‌شود.

رابطهٔ بین زمان امورتایز و زمان واقعی

بر خلاف ظاهر مصنوعیش، مجموع زمان امورتایز یک توالی از عملیات‌ها، حد بالای معتبری برای مجموع زمان واقعی همان توالی از عملیات‌ها به وجود می‌آورد. به عبارت دیگر برای هر مجموعه از اعمال $o_{0},o_{1},\dots$ مجموع زمان امورتایز $\sum _{i}T_{\mathrm {amortized} }(o_{i})$ همیشه بزرگتر مساوی مجموع زمان واقعی $\sum _{i}T_{\mathrm {actual} }(o_{i})$ است. به عبارت بهتر

$\sum _{i}T_{\mathrm {amortized} }(o_{i})=\sum _{i}\left(T_{\mathrm {actual} }(o_{i})+C\cdot (\Phi (S_{i+1})-\Phi (S_{i}))\right)=\left(\sum _{i}T_{\mathrm {actual} }(o_{i})\right)+C\cdot (\Phi (S_{\mathrm {final} })-\Phi (S_{\mathrm {initial} }))\geq \sum _{i}T_{\mathrm {actual} }(o_{i})$

که در آن مجموعهٔ مقادیر تابع پتانسیل تشکیل یک سری تلسکوپی می‌دهند و همهٔ مجموعه مقادیر تابع پتانسیل جز مقدار ابتدایی و انتهایی خنثی می‌شوند و آخرین نا مساوی از آنجایی نتیجه می‌شود که $\Phi (S_{\mathrm {final} })\geq 0$ و $\Phi (S_{\mathrm {initial} })=0$ بنابراین زمان امورتایز می‌تواند برای فراهم کردن پیش گویی دقیق در مورد زمان واقعی یک مجموعه از عملیات‌ها استفاده شود، با وجود این که زمان امورتایز برای یک عملگر مستقل می‌تواند با زمان واقعی عملگر بسیار متفاوت باشد.

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

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

مثال

یک آرایهٔ داینامیک، ساختمان داده ای برای نگهداری یک آرایه از اشیا است، که هم دسترسی رندم به مکان‌های آرایه و همچنین توانایی افزایش طول آرایه به اندازهٔ یک واحد را فراهم می‌کند. این ساختمان داده در جاوا به صورت "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 را در بدترین حالت می‌گیرد، با وجود این که هر عمل مستقل می‌تواند می‌تواند زمان خطی را هزینه کند

کاربردها

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

منابع

http://en.wikipedia.org/wiki/Potential_method