תרגול 12 שאלה 4

מנהל: TA_Isana

שלח תגובה
נועה
הודעות: 29
הצטרף: 00:26 25/10/2009

תרגול 12 שאלה 4

שליחה על ידי נועה » 17:10 26/06/2010

בתרגול 12 בשאלה 4 מחפשים אלגוריתם שלוקח זמן( O(V ולצורך כך משתמשים באלגוריתם ה DFS, אבל זמן הריצה שלו (כפי שנלמד בכיתה) הוא (O(E+V, איך זה יכול להיות?!

תודה.

TA_Ariel
הודעות: 261
הצטרף: 00:53 23/04/2009

Re: תרגול 12 שאלה 4

שליחה על ידי TA_Ariel » 17:22 26/06/2010

אם אין מעגל אז יש רק V-1 צלעות לכן O(V+E)=O(V).
אם יש מעגל אז לכל היותר בצעד הV של האלג' הוא ימצא אותו, ואז הוא עוצר.
לכן האלג' יבצע לכל היותר O(V) פעולות.

נועה
הודעות: 29
הצטרף: 00:26 25/10/2009

Re: תרגול 12 שאלה 4

שליחה על ידי נועה » 17:41 26/06/2010

תודה :)
קצת הרחקתי לכת במחשבה על המקרה הגרוע ביותר...

שלח תגובה

חזור אל “- מבני נתונים 2010”