שאלת מבחן באלגוריתמים - האוניברסיטה הפתוחה 2021 - סיבוכיות

שאלה 2 – תור-קדימויות (אלגוריתמים חמדניים על גרפים) השאלה דנה במימושים שונים לתור-קדימויות עם $n$ מפתחות, במסגרת הפעלת האלגוריתם של Dijkstra או של Prim. מימוש פשוט במיוחד הוא לשמור את כל המפתחות ברשימה דו-כיוונית ללא שום דרישת-סדר (להלן "רשימה". בפרט, הרשימה אינה ממוינת). ערימת-פיבונאצ'י הינה מימוש מחוכם, שאינו נלמד בקורס, אך זמני-הריצה שלו רשומים להלן (למען הדיוק, רשומים מעין זמני-ריצה "ממוצעים", אך ניתן להוכיח כי לעובדה זו אין השפעה על זמן-הריצה הכולל של האלגוריתמים, ולכן יש להתעלם מאבחנה זו). לכל אורך התשובה יש להשמיט את הסימנים האסימפטוטיים $O$. (א) השלימו בטבלה הבאה את זמני-הריצה עבור כל סוג של פעולה. | | רשימה | ערימה-בינארית | ערימת-פיבונאצ'י | |---|---|---|---| | בניית התור | $n$ | $n$ | $n$ | | שליפת מינימום | | $\log n$ | $\log n$ (5 נק׳) | | הקטנת מפתח | | (1 נק׳) | $1$ (9 נק׳) | (ב) בסעיפים (1,2,3) להלן רישמו את זמן-הריצה הכולל שדורש תור-הקדימויות במסגרת הרצת האלגוריתם של Dijkstra או של Prim. ציינו בנפרד את התרומה של כל סוג פעולה, ולא רק את הסכום הסופי. דוגמא לפורמט תשובה של תקין: $m + n\log n + m\log n = \Theta(m\log n)$ (3 נק׳). בסעיפים (4,5) נעדיף מימוש מסוים (על פני מימוש אחר) אם זמן-הריצה האסימפטוטי שלו קטן יותר. (למשל, זמן $m$ עדיף על זמן $m\log n$.) "צפיפות" של גרף פרושה, הקשר האסימפטוטי בין מספר הקדקודים $n = |V|$ לבין מספר הצלעות $m = |E|$ (למשל, $n^{1.4} \leq m \leq n^{1.6}$). בבקשה לא לכתוב נימוקים בסעיפים (1-5), מעבר למה שצוין לעיל. (1) הזמן בערימת-פיבונאצ'י____________________________________________(1 נק׳) (2) הזמן בערימה-בינארית_____________________________________________(1 נק׳) (3) הזמן ברשימה ___________________________________________________(4 נק׳) (4) באילו צפיפויות נעדיף רשימה על פני ערימה-בינארית________________________(6 נק׳) (5) באילו צפיפויות נעדיף ערימת-פיבונאצ'י על פני רשימה_______________________(6 נק׳)

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

פתרון: ### סעיף א' נשלים את זמני הריצה החסרים בטבלה. הסיבוכיות היא עבור תור קדימויות המכיל עד $n$ איברים, כפי שקורה באלגוריתמים של דייקסטרה ופרים. * **רשימה, שליפת מינימום:** כדי למצוא את האיבר עם הערך המינימלי ברשימה לא ממוינת, יש לעבור על כל איברי הרשימה. לכן, הסיבוכיות היא $n$. * **רשימה, הקטנת מפתח:** בהינתן מצביע לצומת ברשימה, פעולת עדכון הערך היא מיידית. לכן, הסיבוכיות היא $1$. * **ערימה-בינארית, הקטנת מפתח:** לאחר הקטנת הערך של מפתח, יש צורך "לבעבע" אותו כלפי מעלה בערימה כדי לשמור על תכונת הערימה. במקרה הגרוע, פעולה זו לוקחת זמן הפרופורציונלי לגובה הערימה. לכן, הסיבוכיות היא $\log n$. הטבלה המלאה: | | רשימה | ערימה-בינארית | ערימת-פיבונאצ'י | |---|---|---|---| | **בניית התור** | $n$ | $n$ | $n$ | | **שליפת מינימום** | $n$ | $\log n$ | $\log n$ | | **הקטנת מפתח** | $1$ | $\log n$ | $1$ | ### סעיף ב' באלגוריתמים של **דייקסטרה** ו**פרים**, מבצעים את הפעולות הבאות על תור הקדימויות: * **בניית התור:** פעולה אחת, המכניסה את כל $n$ הצמתים. * **שליפת מינימום (Extract-Min):** מתבצעת $n$ פעמים, פעם אחת עבור כל צומת. * **הקטנת מפתח (Decrease-Key):** מתבצעת לכל היותר פעם אחת עבור כל קשת, כלומר $m$ פעמים במקרה הגרוע. חישוב זמן הריצה הכולל לכל מימוש: (1) **ערימת-פיבונאצ'י:** זמן הריצה הכולל הוא סכום זמני הפעולות: $1 \cdot n$ (בנייה) $+ n \cdot \log n$ (שליפות מינימום) $+ m \cdot 1$ (הקטנות מפתח). סה"כ: $n + n\log n + m = \Theta(m+n\log n)$. (2) **ערימה-בינארית:** זמן הריצה הכולל הוא: $1 \cdot n$ (בנייה) $+ n \cdot \log n$ (שליפות מינימום) $+ m \cdot \log n$ (הקטנות מפתח). סה"כ: $n + n\log n + m\log n = \Theta(m\log n)$ (בהנחה שהגרף קשיר, $m \ge n-1$). (3) **רשימה:** זמן הריצה הכולל הוא: $1 \cdot n$ (בנייה) $+ n \cdot n$ (שליפות מינימום) $+ m \cdot 1$ (הקטנות מפתח). סה"כ: $n + n^2 + m = \Theta(n^2)$ (כיוון ש-$m=O(n^2)$). (4) **השוואה: רשימה מול ערימה-בינארית:** נעדיף מימוש רשימה ($\\(Theta(n^2)\\)$) על פני ערימה-בינארית ($\\(Theta(m\\log n)\\)$) כאשר זמן הריצה של הרשימה קטן או שווה אסימפטוטית, כלומר כאשר $n^2 = O(m\log n)$. אי-שוויון זה מתקיים כאשר $m\log n \ge c \cdot n^2$ עבור קבוע $c>0$, או $m \ge c \frac{n^2}{\log n}$. לכן, נעדיף רשימה עבור גרפים צפופים מאוד, המקיימים $m = \Omega(n^2/\log n)$. (5) **השוואה: ערימת-פיבונאצ'י מול רשימה:** נעדיף ערימת-פיבונאצ'י ($\\(Theta(m+n\\log n)\\)$) על פני רשימה ($\\(Theta(n^2)\\)$) כאשר זמן הריצה שלה קטן יותר אסימפטוטית, כלומר כאשר $m+n\log n = o(n^2)$. מכיוון ש-$n\log n = o(n^2)$, התנאי שקול ל-$m=o(n^2)$. לכן, נעדיף ערימת-פיבונאצ'י עבור כל הגרפים שאינם צפופים לחלוטין (כלומר, כאשר $m$ אינו $\\(Theta(n^2)\\)$). התשובה היא $m=o(n^2)$.