ערימות פיבונאצ'י/ניתוח לשיעורין
יש לי שאלה כזאת, שאני לא מצליח להבין מה רוצים ממני (אני לא טוב עם ניתוחים לשיעורין...
): נרצה להוסיף את הפעולה הבאה לערימת פיבונאצ'י SortMarkedBy(q) - (כאשר הפרמטר q, היכול להיות שונה בכל קריאה, הוא מספר טבעי כלשהו) הממיינת את הצמתים המסומנים (בעקבות פעולות decrease_key ו delete_key) בערימה. תהי S קבוצת הצמתים שסומנו מאז פעולת SortMarkedBy הקודמת ומסומנים בעת הקריאה הנוכחית, SortMarkedBy ממיינת את מפתחות צמתי S לפי ערכם modulo q ומדפיסה את הרשימה הממוינת. א. הציעו מימוש יעיל של SortMarkedBy. הוכיחו את נכונות האלגוריתם ונתחו יעילותו. ב. תנו חסמים לשיעורין (והוכיחו נכונותם( לפעולות הרגילות על ערימת פיבונאצ'י ביחד עם SortMarkedBy כך שהעלות לשיעורין של SortMarkedBy תהיה O(1). (תנו חסמים לשיעורין נמוכים ככל שתוכלו למצוא ובפרט כאלו שהעלות לשיעורין של אף פעולה לא תעלה על O(log
) והעלות לשיעורין של insert לא תעלה על O(1)). ג. האם ניתן לפתור את סעיף ב' כך שהעלות לשיעורין של שאר הפעולות (הפעולות המקוריות שערימת פיבונאצ'י תומכת בהן) תהיה זהה (אסימפטוטית) לעלותן לשיעורין המקורית? נמקו תשובתכם. מימשתי את זה בסיבוכיות של O של N (כשN זה גודל הערימה) - הפונקציה תשתמש בטבלת גיבוב בגודל Q, לפני הריצה העיקרית הפונקציה תפרק את הטבלה מהריצה הקודמת ותוסיף את הצמתים המסומנים לS (בתנאי שהם עדיין מסומנים), ואז תרוץ על S ותכניס כל מפתח לתא בטבלה לפי פונקציה MOD Q מפתח = תא. על מה לבסס ניתוח לשיעורין אין לי מושג
רמזים יתקבלו בברכה
יש לי שאלה כזאת, שאני לא מצליח להבין מה רוצים ממני (אני לא טוב עם ניתוחים לשיעורין...
) והעלות לשיעורין של insert לא תעלה על O(1)). ג. האם ניתן לפתור את סעיף ב' כך שהעלות לשיעורין של שאר הפעולות (הפעולות המקוריות שערימת פיבונאצ'י תומכת בהן) תהיה זהה (אסימפטוטית) לעלותן לשיעורין המקורית? נמקו תשובתכם. מימשתי את זה בסיבוכיות של O של N (כשN זה גודל הערימה) - הפונקציה תשתמש בטבלת גיבוב בגודל Q, לפני הריצה העיקרית הפונקציה תפרק את הטבלה מהריצה הקודמת ותוסיף את הצמתים המסומנים לS (בתנאי שהם עדיין מסומנים), ואז תרוץ על S ותכניס כל מפתח לתא בטבלה לפי פונקציה MOD Q מפתח = תא. על מה לבסס ניתוח לשיעורין אין לי מושג