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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

תיאור השיטה[עריכת קוד מקור | עריכה]

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

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

(c'i=ci+Φ(Di)-Φ(Di-1

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

\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)

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

דוגמה[עריכת קוד מקור | עריכה]

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