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

[sf8f]

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

אני צריך אלגוריתם שעובד על גרף אציקלי מכוון (DAG) וסופר את מספר המסלולים קיימים מקודקוד A ל-B. אין צורך לציין את המסלולים. צריך זמן ריצה של O של E+V. האלגוריתם שחשבתי עליו: PATHS(A,B p=0 for each outgoing edge E from A if E connects to B then P=P+1 else P=P+PATHS(E.destination,B return P אבל אני מתקשה לנתח את זמן הריצה. הייתי רוצה לדעת מה זמן הריצה של האלגוריתם (עם הסברים אם אפשר) וכמו כן לדעת אם עמדתי במשימה. תודה

 

[ron369]

אציקלי?

שאין בו מעגלים?

 

[GuestOfHonor]

../images/Emo45.gif

ואם השאלה באה מאיפה שאני חושב שהיא באה, אז מותר להשתמש בToplogical sort ואפילו רצוי

 

[kivatinetz]

DFS

אולי אתה יכול לעשות DFS מהקודקוד A. DF עובדת בזמן O שך E+V.

 

[sf8f]

תודה על העצות רבותיי

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

 

[Blade2]

איך שאני רואה את זה, זה ליניארי

בגלל שזה DAG, אין מעגלים, מובטח לך שתבקר בכל צומת פעם אחת לכל היותר. לכן אתה גם תעבור על כל קשת פעם אחת לכל היותר. אתה מבצע פעולות בזמן קבוע בכל קשת, ולכן בסך הכל: O(V+E) zz