|
|
עמוד:296
הוכחה כידוע , עבור גרף , G שהנו גרף מכוון , הסכום של אורכי כל רשימות הסמיכות הוא . | £ | הלולאה הראשונה ( for ) מתבצעת בזמן ? O (\ V \) הלולאה השנייה ( for ) מתבצעת בזמן ? 0 {\ E \) הלולאה השלישית ( for ) מתבצעת בזמן ? 0 (\ v \) כיוון שהגישה לאינדקס מסוים במערך אורכת זמן של , 0 ( 1 ) וגם הפעולה - הוספת איבר לסוף התור - אורכת זמן של . 0 ( 1 ) מספר הצעדים בלולאה הרביעית ( while ) הוא כסכום האורכים של כל הרשימות הסמוכות , שהוא . 0 (| £ |) הלולאה החמישית ( for ) מתבצעת בזמן 0 (| V |) וביחד , סיבוביות זמן הריצה של האלגוריתם הנדון היא י 0 (\ V \ + \ E \) = 0 ( max (| V | , | £ |)) להלן גרסה שנייה של האלגוריתם למיון טופולוגי באמצעות סריקת גרף לעומק ! TP _ Sort ( Graph G ) . 1 קרא לשגרה DFS ( G ) כאשר השגרה DFS מחשבת את [ OiW המציין את מועד הסיום של הקדקוד , v עבור כל קדקוד ; v כאשר הטיפול בקדקוד v מסתיים , אז שים אותו בחזית הרשימה המייצגת את המיון הטופולוגי . , 2 הדפס את הרשימה המייצגת את המיון הטופולוגי . קל לראות שסיבוכיות זמן הריצה של האלגוריתם הזה היא כסיבוכיות הריצה של השגרה DFS שהיא : . O (| vj + \ E \ ) דוגמה : נתון הגרף שלהלן :
|
|