תרגול 12 שאלה 4

מנהל: TA_Isana

תרגול 12 שאלה 4

הודעהעל ידי נועה » 16:10 26/06/2010

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

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

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

הודעהעל ידי TA_Ariel » 16:22 26/06/2010

אם אין מעגל אז יש רק V-1 צלעות לכן O(V+E)=O(V).
אם יש מעגל אז לכל היותר בצעד הV של האלג' הוא ימצא אותו, ואז הוא עוצר.
לכן האלג' יבצע לכל היותר O(V) פעולות.
TA_Ariel
 
הודעות: 261
הצטרף: 23:53 22/04/2009

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

הודעהעל ידי נועה » 16:41 26/06/2010

תודה :)
קצת הרחקתי לכת במחשבה על המקרה הגרוע ביותר...
נועה
 
הודעות: 29
הצטרף: 00:26 25/10/2009


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

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ואורח אחד

cron