שיטת הפוטנציאל – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
יצירת דף עם התוכן "בתורת הסיבוכיות, '''שיטת הפוטנציאל''' היא שיטה לחישוב עלות לשיעורין של..." |
אין תקציר עריכה |
||
שורה 7:
:(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>, כלומר שהניתוח יביא לנו [[חסם עליון]] על מספר הפעולות.
| |||