מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/חיפוש רוחבי/תרגילים/ סדר הדפסת הצמתים וזמן הריצה/תשובה v2

סדר ההדפסות

• תחילה יודפס 1 כמובן.
• באיטרציה הראשונה של 8-14, התור יכיל את 1.‏ 10-14 ידפיסו את 2 ו6 ויכניסו אותם לתור (בסדר הזה).
• באיטרציה השניה, 2 יהיה בראש התור. 3 יודפס ויוכנס לתור.
• באיטרציה השלישית, 6 יהיה בראש התור. 5 ו7 יודפסו ויוכנסו לתור (בסדר הזה). כעת התור יכיל את 3, 5, ו7 (3 בראש התור)
• נמשיך כך הלאה.

הצמתים יודפסו בסדר הבא (משמאל לימין): $\displaystyle 1,2,6,3,5,7,4$.

ניתוח זמן הריצה

• 1-2 ו5-7 הן $\displaystyle O(1)$
• 3-4 הן $\displaystyle \Theta (|V|)$.
• הלולאה 8-14 מתבצעת בדיוק פעם אחת עבור כל צומת. בפרט, הבדיקה ב8 והפעולה ב9 עולות $\displaystyle \Theta (|V|)$.
• באופן דומה, הלולאה 10-14 מתבצעת בדיוק פעם אחת עבור כל זוג $\displaystyle u,v$ כך ש$\displaystyle (u,v)\in E$. הלולאה תורמת לכן $\displaystyle \Theta (|E|)$.

שימו לב: חשוב להבין שלמרות שהלולאה 10-14 נמצאת בתוך הלולאה 8-14, זמן הריצה של 10-14 אינו המכפלה $\displaystyle \Theta (|V|\cdot |E|)$. ניזכר בניתוח זמן הריצה של לולאות. הלולאה החיצונית רצה על כל הצמתים. הלולאה הפנימית רצה, לכל צומת, על הקשתות היוצאות ממנה. לכן הלולאה הפנימית רצה בדיוק $\displaystyle \Theta (|E|)$ פעמים.

הסיבוכיות, לכן, היא $\displaystyle O(1)+\Theta (|V|)+\Theta (|V|)+\Theta (|E|)=\Theta (|V|+|E|)$.