עזרה באלגוריתם

[xrat]

עזרה באלגוריתם

אהלן, נתונה לי רשימה מקושרת(חד כיוונית) מעגלית, שהמעגל הוא לאו דווקא לאיבר הראשון אלא האחרון מצביע לאיבר כלשהוא ברשימה.אני צריך למצוא אלגוריתם שמקבל מצביע לראש הרשימה ולאיבר כלשהוא בתוך המעגל, ומוצא את האיבר הראשון במעגל, כל זה בסיבוכיות o(nlgn) הסיבוכיות הנ"ל מרמזת שהאלגוריתם הבנאלי לרוץ בלולאה על המעגל ולקדם כל פעם את המצביע לראש הרשימה לא יעיל מספיק(כי זה o(n^2) למישהו יש רעיון? איך לחלק את זה כל איטרציה ל2 כדי להשיג nlgn?

 

[Zack DA]

רמז, נסה להזיז אותם ביחד לפי

חוקיות כלשהי.

 

[xrat]

לא הבנתי את הרמז...

לא הבנתי מה ייתן לי להזיז את שניהם, יש לך אולי אפשרות להרחיב?...

 

[Zack DA]

זו כל הפואנטה ברמז ../images/Emo13.gif

 

[ChipsMan]

הממ..

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

 

[xrat]

סליחה, אבל אכן...

יש הגבלה על זיכרון, צריך להיות (o(1, ולכן זה קצת יותר קשה...

 

[gmorphus]

לא טוב...

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

 

[DNile]

כן נותנים מצביע לאיבר במעגל.

 

[gmorphus]

מה פתאום?

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

 

[הצלוי]

הנה:

"צריך למצוא אלגוריתם שמקבל מצביע לראש הרשימה ולאיבר כלשהוא בתוך המעגל" יש לך איבר בתוך המעגל. אתה צריך למצוא את האיבר הראשון במעגל.

 

[הצלוי]

אולי משהו כזה?

הבעיה באלגוריתם הבנאלי זה שאנחנו בודקים כל איבר ברשימה אם הוא תחילת המעגל- וכל בדיקה לוקחת o. לכן סך הכל זמן הריצה יוצא o(n^2) אז אולי אפשר לבדוק רק lgn איברים... בהתחלה נמצא את הגודל המקסימלי של הרשימה _ללא המעגל_ (מה האפשרויות שלנו). זה אפשר לעשות ע"י יצירת מצביע אינדקס שיספור כמה איברים יש מתחילת הרשימה עד לאיבר השני שנתנו לך בתוך המעגל. נשמור את "מספר האפשרויות לתחילת המעגל" במשתנה Num למשל. אוקיי, עכשיו כל פעם נבדוק האם האיבר הNum נמצא במעגל- o (ריצה על כל המעגל). כל פעם שזה יהיה נכון (זה בטוח יהיה נכון בהתחלה כי אנחנו הגענו עד לאיבר שנמצא בתוך המעגל), נחלק את Num ב-2 ונבדוק עבור האיבר הזה. זה די מזכיר חיפוש בינארי... בכל מקרה, כל פעם שנסרוק את המעגל זה יהיה o ואנחנו בודקים lg איברים כמו בחיפוש בינארי. כולל מציאת הNum ההתחלתי זמן הריצה יהיה: o(n+nlgn) = o(nlgn) עם o(1).

 

[Zack DA]

לא... מה שכתבת לא נכון....

תסביר שוב הפעם בצורה ברורה...

 

[הצלוי]

שוב, הפעם אנסה יותר ברור...

חלק ראשון: אנחנו מתחילים עם שני מצביעים לרשימה, נכון? אחד לתחילתה ושני איפשהוא במעגל. בודקים כמה איברים יש ביניהם. זה פשוט ע"י סריקה מהראשון עד לשני וספירה עם Counter. נשמור את המספר הזה במשתנה Num. זמן ריצה: O חלק שני- יש לנו את הפונקציה הבאה: isInCircle(object)- מקבל מצביע לאיבר ברשימה ומחזיר האם הוא בתוך המעגל. זה קצת יותר מורכב- ניצור שני מצביעים אינדקסים i, j שיצביעו לאיבר _הבא אחרי_ object. הם יסרקו את המעגל בלולאה: כל עוד (i לא מצביע לj וגם j לא מצביע לi) אם אחד מהם מצביע לobject, תחזיר "כן- האיבר בתוך המעגל". תקדם את i בשני איברים, ותקדם את j באיבר אחד. "תחזיר לא- האיבר לא בתוך המעגל". אוקיי, isInCircle קצת מסובך אולי.. אני יכול להסביר אותו יותר בהודעה אחרת אם אתם רוצים. בהנחה שהיא מובנת ועובדת (זמן ריצה o), עכשיו נעשה כך: חלק שלישי: התכל'ס

זוכרים את Num? יפה. האיבר הNum נמצא בתוך המעגל (נתון)- כי ספרנו עד האיבר שנמצא בתוך המעגל. נספור Num/2 איברים מתחילת הרשימה, ונבדוק (בעזרת isInCircle) האם האיבר הזה בתוך המעגל. אם הוא כן, אז הרגע כיסינו חצי מהאפשרויות שלנו: כל האיברים מNum/2 עד Num נמצאים בתוך המעגל ולכן הם בטוח לא מצביעים לתחילת המעגל. הלאה. שוב נחלק: Num/4. נבדוק שוב האם האיבר הזה בתוך המעגל, וכך הלאה עד שנגיע לאיבר שאינו במעגל... בדיוק כמו חיפוש בינארי- עכשיו נתקדם קצת קדימה עד שנגיע שוב לאיבר שכן במעגל- וזה אומר שהאיבר הנוכחי מצביע לתחילת המעגל. התהליך הזה בדק lgn איברים (כמו חיפוש בינארי). לכל איבר ביצענו isInCircle, ולכן זמן הריצה הכולל הוא o(nlgn). אם זה עדיין לא מובן, תגידו לי איזה חלק (ראשון, שני או שלישי) לא מובן..

 

[Zack DA]

כמה הערות:

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

 

[הצלוי]

אוקיי, טעות../images/Emo13.gif

כשניסיתי לכתוב בפסאודו קוד גיליתי שזמן הריצה הוא כנראה עדיין o(n^2), אז עזבו את הרעיון שלי. אני ניסיתי להפעיל מעיין חיפוש בינארי על הרשימה- לפסול חצי מהאיברים כל פעם. הבעיה היא שזה רשימה מקושרת ולא מערך, ולכן רק לסרוק את האיברים מבלי לבדוק אותם ייקח כנראה o(nlgn) (במקום lgn במערך), ולכן זה לא יהיה יותר טוב מהאלגוריתם הבנאלי.... דרך אגב, לא שיניתי גרסה בצורת הסריקה, פשוט פרטתי אותה יותר.. אבל תמשיכו לנסות!

 

[Zack DA]

שמח שעלית על זה לבד ../images/Emo45.gif

אבל אתה מתקדם. המשך כך.

 

[xrat]

רק כדי שלא תחשבו

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

 

[hope2drive]

הפתרון שלכם דווקא נכון

לפי דעתי. נכון, בשביל לקדם פוינטר ל"אמצע" צריך O של n צעדים, אבל זה לא משנה, כיוון שזה יתבצע רק O של Logn פעמים. במילים אחרות: יהיו logn איטרציות, כאשר בכל איטרציה עושים את 3 הדברים הבאים: 1- סיבוב על המעגל בשביל לבדוק אם אנחנו בתוכו. 2- קידום פוינטר (זה שמחוץ למעגל או זה שבתוך המעגל) למקום האמצעי 3- קידום פוינטר לאמצע ביניהם כל אחת מהפעולות האלו היא O של n, ואחריה כן הקטנו את הבעיה פי 2. חצי מהאיברים שהיו ביניהם כבר לא באים בחשבון. הנה הפסודו-קוד (הפתרון שלכם כמובן): i פוינטר לתחילת הרשימה j פוינטר לאיבר במעגל k פוינטר עזר 1. מדוד את המרחק בין i ל-j ושמור אותו במשתנה NUM 2. k=i 3. קדם את k ב-NUM/2 איברים 4. בדוק אם k בתוך המעגל (פשוט עם פוינטר נוסף שיתחיל מ-j ויעשה סיבוב עד שיחזור ל-j או שיתקל ב-k.) 5. אם כן: j=k (אם j==i+1 סיימנו) NUM=NUM/2 חזור לסעיף 2. 6. אם לא: i=k (אם j==i+1 סיימנו) NUM=NUM/2 חזור לסעיף 3. אז ככה: סעיפים 3 ו-4 לוקחים O של n , אבל בגלל ש- NUM קטן פי 2 בכל שלב הם יתבצעו logn פעמים לכל היותר. תקנו אותי (וקבלו התנצלותי) אם יש לי טעות (וזה יכול להיות). אבל ככה נראה לי.

 

[xrat]

על פניו

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

 

[hope2drive]

אני מקווה שצחי יסלח לי ../images/Emo8.gif

אבל לדעתי הוא התבלבל עם חידה אחרת, האומרת: "קבל רשימה מקושרת (עם מצביע לתחילתה בלבד) וקבע האם יש בה מעגל". יש לזה פתרון עם טריק נחמד, והסיבוכיות שלו היא O של n בלבד. (לא Onlogn) אני לא אגלה לך בשביל לא לקלקל אם אתה רוצה לנסות לבד. וצחי, אם טעיתי והתכוונת למשהו אחר - סליחה!