שיטת הפוטנציאל

בתורת הסיבוכיות, שיטת הפוטנציאל היא שיטה לחישוב עלות לשיעורין של סדרת פעולות על מבנה נתונים.

תיאור השיטה

בשיטה מגדירים "פונקציית פוטנציאל", Φ, המקבלת מצב של המבנה ומחזירה מספר חיובי שבאופן אינטואיטיבי ניתן לחשוב עליו כעל "אנרגיה פוטנציאלית" של המצב.

את העלות לשיעורין מחשבים בעזרת השינוי בפוטנציאל, יחד עם העלות האמיתית. כלומר, אם נסמן את המצבים ב-D_i, את העלות האמיתית של המעבר מ-D_i-1 ל-D_i ב-c_i ואת העלות לשיעורין ב-c'_i אז מתקיים:

(c'_i=c_i+Φ(D_i)-Φ(D_i-1

את העלות לשיעורין של כל סדרת הפעולות מחשבים באמצעות טור טלסקופי:

${\displaystyle \sum _{i=1}^{n}c'_{i}=\sum _{i=1}^{n}(c_{i}+\Phi (D_{i})-\Phi (D_{i-1}))=\sum _{i=1}^{n}(c_{i})+\Phi (D_{n})-\Phi (D_{0})}$

בהגדרת הפוטנציאל דורשים שהפוטנציאל של המצב ההתחלתי יהיה 0, ושל כל מצב אחר יהיה חיובי. בצורה כזאת מובטח לנו שמתקיים ${\displaystyle \sum _{i=1}^{n}c'_{i}\geq \sum _{i=1}^{n}c_{i}}$, כלומר שהניתוח יביא לנו חסם עליון על מספר הפעולות.

דוגמה

נניח שנתון לנו מונה בינארי, כלומר מערך שאיבריו הם 0 או 1 כך שהם מייצגים מספר בבסיס בינארי. נרצה לחשב את העלות לשיעורין של n פעולות של הוספת אחד למונה (שמאותחל בהתחלה ל-0). ניתוח נאיבי הוא שבמקרה הגרוע פעולה תחליף את כל הביטים (מעבר מרצף אחדות לאחד ואחריו אפסים) כלומר n פעמים פעולות ב-(O(n שזה (O(n². אלא שניתוח זה הוא לא הדוק, כיוון שרוב הפעולות דורשות זמן קצר בהרבה. נחשב בעזרת שיטת הפוטנציאל: נגדיר פונקציית פוטנציאל בצורה הבאה: הפוטנציאל של מצב יהיה מספר האחדות בו. כעת, אם נסמן את מספר האחדות בקצה המצב ה-i ב-t_i, אז העלות של להוסיף אחד תהיה להפוך את כל האחדות לאפסים ואת האפס שמשמאלם להפוך ל-1, כלומר c_i=t_i+1. נשים לב שמצב זה הורדנו t_i אחדות והוספנו אחד, כלומר הקטנו את הפוטנציאל ב-t_i-1. מקבלים: c'_i=c_i+Φ(D_i)-Φ(D_i-1)=t_i+1-(t_i-1)=2 כלומר העלות לשיעורין של כל פעולה היא 2 ולכן העלות הממוצעת היא לא יותר מ-2, כלומר ב-(O(1.