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

השאלה עוסקת במימושים שונים לתור-קדימויות עם $n$ מפתחות, במסגרת הפעלת האלגוריתם של Dijkstra או של Prim. שני מימושים: **רשימה** דו-כיוונית לא ממוינת, **ערימה-בינארית**, ו**ערימת-פיבונאצ'י** (שזמני-הריצה שלה amortized). לכל אורך התשובה השמיטו את הסימנים האסימפטוטיים $O,\Theta$. נסמן $n=|V|$, $m=|E|$. **(א)** השלימו את זמני-הריצה של כל פעולה בכל מימוש. **(ב)** רשמו את זמן-הריצה **הכולל** של Dijkstra/Prim בכל מימוש (בניית התור $+\ n\cdot$שליפת-מינימום $+\ m\cdot$הקטנת-מפתח), וקבעו לאילו צפיפויות עדיף כל מימוש.

רמז: הזמן הכולל הוא $\text{build}+n\cdot(\text{extract-min})+m\cdot(\text{decrease-key})$. הציבו את ערכי הטבלה, והשוו $n^2$ מול $m\log n$ מול $m+n\log n$ לפי $m$.

פתרון: **(א) טבלת זמני-הריצה** (לכל פעולה): | פעולה | רשימה לא ממוינת | ערימה בינארית | ערימת פיבונאצ'י | |---|---|---|---| | בניית התור | $n$ | $n$ | $n$ | | שליפת מינימום | $n$ | $\log n$ | $\log n$ | | הקטנת מפתח | $1$ | $\log n$ | $1$ | (ערימת-פיבונאצ'י: שליפת-מינימום $\log n$ ו-decrease-key $1$ הם זמנים **amortized**.) **(ב) זמן ריצה כולל** $= \text{build} + n\cdot\text{extract-min} + m\cdot\text{decrease-key}$: - **רשימה:** $n + n\cdot n + m\cdot 1 = n^2$. - **ערימה-בינארית:** $n + n\log n + m\log n = m\log n$ (עבור $m\ge n$). - **ערימת-פיבונאצ'י:** $n + n\log n + m\cdot 1 = m + n\log n$. **מתי כל מימוש עדיף:** - **רשימה מול ערימה-בינארית:** רשימה ($n^2$) עדיפה על בינארית ($m\log n$) כאשר $n^2 < m\log n$, כלומר בגרפים **צפופים** מאוד: $m = \omega\!\left(\frac{n^2}{\log n}\right)$ (וכזכור $m\le n^2$). לגרפים דלילים-בינוניים הבינארית עדיפה. - **ערימת-פיבונאצ'י מול רשימה:** פיבונאצ'י ($m+n\log n$) עדיפה **לכל צפיפות**, שכן תמיד $m\le n^2$ וגם $n\log n\le n^2$, ולכן $m+n\log n = O(n^2)$. - (בונוס — פיבונאצ'י מול בינארית: פיבונאצ'י לעולם אינה גרועה יותר אסימפטוטית, ועדיפה ממש כאשר $m=\omega(n)$.)