עמוד 1 מתוך 1

תרגול 12 שאלה 4

הודעהפורסם: 16:10 26/06/2010
על ידי נועה
בתרגול 12 בשאלה 4 מחפשים אלגוריתם שלוקח זמן( O(V ולצורך כך משתמשים באלגוריתם ה DFS, אבל זמן הריצה שלו (כפי שנלמד בכיתה) הוא (O(E+V, איך זה יכול להיות?!

תודה.

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

הודעהפורסם: 16:22 26/06/2010
על ידי TA_Ariel
אם אין מעגל אז יש רק V-1 צלעות לכן O(V+E)=O(V).
אם יש מעגל אז לכל היותר בצעד הV של האלג' הוא ימצא אותו, ואז הוא עוצר.
לכן האלג' יבצע לכל היותר O(V) פעולות.

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

הודעהפורסם: 16:41 26/06/2010
על ידי נועה
תודה :)
קצת הרחקתי לכת במחשבה על המקרה הגרוע ביותר...