הצגת המקור של הדף "שיטת הפוטנציאל"

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

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

את העלות לשיעורין מחשבים בעזרת השינוי בפוטנציאל, יחד עם העלות האמיתית. כלומר, אם נסמן את המצבים ב-D<sub>i</sub>, את העלות האמיתית של המעבר מ-D<sub>i-1</sub> ל-D<sub>i</sub> ב-c<sub>i</sub> ואת העלות לשיעורין ב-c'<sub>i</sub> אז מתקיים:
:(c'<sub>i</sub>=c<sub>i</sub>+Φ(D<sub>i</sub>)-Φ(D<sub>i-1</sub>
את העלות לשיעורין של כל סדרת הפעולות מחשבים באמצעות [[טור טלסקופי]]:
:<math>\sum_{i=1}^nc'_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)</math>

בהגדרת הפוטנציאל דורשים שהפוטנציאל של המצב ההתחלתי יהיה 0, ושל כל מצב אחר יהיה חיובי. בצורה כזאת מובטח לנו שמתקיים <math>\sum_{i=1}^nc'_i\ge\sum_{i=1}^nc_i</math>, כלומר שהניתוח יביא לנו [[חסם עליון]] על מספר הפעולות.

==דוגמה==
נניח שנתון לנו מונה בינארי, כלומר [[מערך (מבנה נתונים)|מערך]] שאיבריו הם 0 או 1 כך שהם מייצגים מספר ב[[בסיס בינארי]]. נרצה לחשב את העלות לשיעורין של n פעולות של הוספת אחד למונה (שמאותחל בהתחלה ל-0). ניתוח נאיבי הוא שבמקרה הגרוע פעולה תחליף את כל הביטים (מעבר מרצף אחדות לאחד ואחריו אפסים) כלומר n פעמים פעולות ב-(O(n שזה (O(n<sup>2</sup>. אלא שניתוח זה הוא לא הדוק, כיוון שרוב הפעולות דורשות זמן קצר בהרבה. נחשב בעזרת שיטת הפוטנציאל: נגדיר פונקציית פוטנציאל בצורה הבאה: הפוטנציאל של מצב יהיה מספר האחדות בו. כעת, אם נסמן את מספר האחדות בקצה המצב ה-i ב-t<sub>i</sub>, אז העלות של להוסיף אחד תהיה להפוך את כל האחדות לאפסים ואת האפס שמשמאלם להפוך ל-1, כלומר c<sub>i</sub>=t<sub>i</sub>+1. נשים לב שמצב זה הורדנו t<sub>i</sub> אחדות והוספנו אחד, כלומר הקטנו את הפוטנציאל ב-t<sub>i</sub>-1. מקבלים: c'<sub>i</sub>=c<sub>i</sub>+Φ(D<sub>i</sub>)-Φ(D<sub>i-1</sub>)=t<sub>i</sub>+1-(t<sub>i</sub>-1)=2 כלומר העלות לשיעורין של כל פעולה היא 2 ולכן העלות הממוצעת היא לא יותר מ-2, כלומר ב-(O(1.

[[קטגוריה:סיבוכיות]]