|
|
עמוד:242
צעד 1 1 . 1 נניח שהקבוצה T ממומשת בעזרת מערך . על כן , צעד זה דורש זמן של ? O (\ v \) 1 . 2 נניח שהקבוצה P ממומשת בעזרת מערך . על כן צעד זה דורש זמן של . 0 ( 1 ) 1 . 3 בהמשך להנחה 1 . 1-שב בצעד 1 . 1 ניתן לשמור מידע על מיקומו של הקדקוד . K על כן , צעד זה דורש זמן של . 0 ( 1 ) כיוון שצעד 1 מתבצע \ V \ פעעים , הזמן הכולל שצעד 1 דורש הוא . O \ V \ צעד 2 נניח שהגרף מיוצג בעזרת רשימות סמיכות . כידוע , אם הגרף G מכוון , סכום האורכים של כל רשימות הסמיכות הוא \ E \ וכאשר הגרף G הוא בלתי מכוון , סכום האורכים של כל רשימות הסמיכות הוא 2 \ E \ מכל מקום , סכום האורכים של רשימות הסמיכות הוא ? 0 (\ E \) ברור כי באלגוריתם הנדון , כל קדקוד של גרף מוכנס לקבוצה P פעם אחת , כך שכל קשת ברשימת הסמיכות נבחנת בדיוק פעם אחת במהלך האלגוריתם . לאור האמור לעיל , צעד 2 מתבצע בסך הכל 0 (\ E \) פעמים . מסקנה : סיבוכיות זמן הריצה של אלגוריתם דיק 0 ג 1 רה היא : O \ V \ + \ E \ = O {\\ tf ) : mj » n למעשה , ניתן להשיג זמן ריצה של 0 (| £ | 10 g | V |) כאשר הקבוצה T ממומשת בעזרת מבנה נתונים מסוים הנקרא "ערמה ( heap ) . "בינרית להלן מספר עובדות בקשר לערמה הבינרית : א . בניית ערמה דורשת זמן של . 0 (\ V \) ב . איתור וסילוק האיבר הקטן ביותר שבערמה דורשים זמן של . 0 ( log )| V |) ג . צעד 2 . 1 מתבצע בזמן . 0 ( 10 g )| V |) צעד 1 מתבצע \ V \ פעמים , ובכל צעד נדרש זמן . 0 ( 10 g )| V |) לכן הזמן הכולל של צעד 1 הוא . 0 (| V | 10 g )| V |)
|
|