זה בסדר אם טיול מקודקוד לקודקוד בגרף יעלה זמן לינארי?

[Mark]

אם טיול מקודקוד יעלה זמן לינארי אם יש בינם צלע בגרף

בזמן
O(n)
כגודל הקודקודים.

מומלץ לעשות פחות מליניארי?
יהיה הורדת מיקוד על זה?

--
Subscription settings: http://groups.google.com/group/oop1_hadasa/subscribe?hl=iw

[Gilad or]

מארק, האם אתה מתכוון שטיול מקדקד לקדקד הוא לינארי כך שטיול בכל הגרך הוא בזמן ריבועי?

בתאריך 26 באפריל 2010 19:53, מאת Mark <marks...@gmail.com>:

--
Gilad or
גילעד אור

[Mark]

סוג של..
התכוונתי שאם אתה שומר שכנים של קודקוד במטריצה בוליינית, אז למשל ב
DFS
אבור קודקוד מסוים, כדי לבקר את כל שכניו נעשה
n
בדיקות כי המערך השכנים כגודל הקודקודים,
אם אני ישמור את השכנים ברשימה מקושרת אז אני יעשה הרבה פחות בדיקות אם
אין הרבה שכנים כלומר
O(| Adj(u) |) , u<-V

אבל הסתדרתי כבר ועשיתי בדרך שנייה

[Gilad or]

תקן אותי אם אני טועה. אם אתה רץ על רשימות השכנים בDFS, אתה רת עבור קדקד בזמן ריבועי, אלא אם כן אתה שומר מצביע למיקום שבו הפסקת, 

ובהתחשב בפעולת DFS מקוטעת, שאחרי כל עלה שמצאת את יוצא מהפונקציה וממחזר את העירמה, אתה חייב או לשמור את הפוינטרים במחסנית - פתרון יעיל, או שתכל פעם תרוץ על רשימת השכנים כדי להמשיך מאיפה שהספקת - לא יעל בעליל - זמן ריבועי.

אולי עשית DFS על כל הגרף כמה פעמים ואז לא הייתה בעיית קיטוע, לא יודע.  הכי חשוב לא להרים את זמן הריצה..

בתאריך 26 באפריל 2010 22:35, מאת Mark <marks...@gmail.com>:

[Mark]

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

שים לב שיכול וגם אולי יקרה מצב בו כמעת כל דוק נחתך עם כל דוק
ואז מספר הצלעות יהיה ריבועי, ואז בי אפ אס יהיה ריבועי

[Gilad or]

אני חושב שמהוכחת הBFS זה לא ייתכן. כמו כן כל דוק נבדק פעם אחת, שכן לאחר שגילו אותו הוא מסומן באפור.

בתאריך 27 באפריל 2010 00:13, מאת Mark <marks...@gmail.com>:

[Mark]

זמן ריצה של די אפ אס הוא
O(|E|+|V|)
ייתכן גרף שבו למשל מקודקוד ראשון יש צלע לכל קודקודים
מקודקוד שני יש צלעות לכולם פרט לראשון
משלישי יש לכולם פרט לראשון ושני וכו
ואז יש
O(V^2)
צלעות לא? כלומר זמן ריצה
O(V^2)

[Gilad or]

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

בתאריך 27 באפריל 2010 00:54, מאת Mark <marks...@gmail.com>:

[Mark]

התכוונתי לינארי מקודקוד לקודקוד,
לא לדי אפ אס
בלי קשר להתגלויותת זמן ריצה של די אפ אס תמיד
O(|V|+|E|)
אם מספר צלעות הוא ריבועי
אז גם זמן ריצה
נכון קודקודים כאן מתגלים
אבל כדי להאפיר ולהשחיר קודקוד אתה חייב לרוץ פעם אחד על כל שכניו ולבדוק
את צבעם
אם אני למשל שומר שכנים במטריצה בגודל של מס קודקודים
אז זמן ריצה יהיה ריבועי

[Gilad or]

אם מספר הצלעות הוא ריבועי? מס הצלעות הוא תמיד n לא?

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

לילה טוב 

בתאריך 27 באפריל 2010 01:00, מאת Mark <marks...@gmail.com>:

[Mark]

את כל קודקוד אתה מאפיר ומשחיר פעם אחד, לכן עבור כל קודקוד עושה בדיקה
של כל שכניו

[Gilad or]

בוא נדבר על זה מחר, אני זז לישון. אני בטוח שיצא לך משהו מקורי ומעניין.

בתאריך 27 באפריל 2010 01:05, מאת Mark <marks...@gmail.com>: