פונקציית פוטנציאל

Summary:

שאלה בסיסית על פונקציית פוטנציאל

פונקציית פוטנציאל

Ittai Zeidman 15 Feb 2010 16:04

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

השאלה:
נתונה ערימה בינרית רגילה בת אן איברים בתומכת בפעולות הכנסה והוצאת מינימום בזמן או של לוג אן במקרה הגרוע
מצא פונקצית פוטנציאל כך שהעלות לשיעורין של הכנסה תהיה או של לוג אן והעלות לשיעורין של הוצאת מינימום תהיה או של 1
והראה שהיא פועלת כהלכה

Re: פונקציית פוטנציאל

Yahav 15 Feb 2010 16:45

השיטה במקרים כאלה לעבור מבנק לפוטנציאל, היא להגדיר
פונקציית פוטנציאל שתהיה סכום מאזן הבנק.
אם כאן, לאיבר ה-$i$ יש $\log(i)$$ מטבעות,
נוכל להגדיר פוטנציאל בעזרת הסכום
$\sum_{i=1}^n \log (i)$