שאלה למוחות הפורום,

[johnny d]

שאלה למוחות הפורום,

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

 

[shirbi]

מה לגבי ספירה?

האם מותר לספור כמה איברים יש בכל רשימה או שזה נחשב לזיכרון לוגריתמי ולכן אסור? אם לדוגמה, ספרת וגילית שברשימה הראשונה יש 100 איברים וברשימה השניה יש 4 איברים, אז אתה יכול לדעת שאו שהאיבר ה 97 ברשימה הראשונה והאיבר ה 1 ברשימה השניה נחתכים, או האיבר 98 ו ה 2 בהתאמה או ה 99 וה 3 או ה 100 וה- 4. כלומר, סה"כ, תצטרך מספר ליניארי של השוואות.

 

[johnny d]

הרשימה יכולה להיחתך בכל מקום

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

 

[vinney]

אם הנחה סמויה

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

 

[johnny d]

זה הנחה דיי כבדה

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

 

[shirbi]

לא הבנתי את הדוגמה שלך

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

 

[johnny d]

אוקי,

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

 

[shirbi]

לא מסכים.

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

 

[Fractal]

תנסה את הכיוון של להפוך רשימה אחת

סיבוכיות לינארית במקום קבוע. אם יש לנו רשימות L1 L2. מה יקרה לאיבר האחרון של L2 אם נפוך את L1 ?

 

[johnny d]

אתה קצת מתבלבל בסיבוכיות המקום.

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

 

[Fractal]

סיבוכיות מקום

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

 

[gil levi]

לא הבנתי משהו.

נחתכות = יש להן חוליה משותפת? אם כן, אז האם מאותה חוליה משותפת והלאה הן מתלכדות?

 

[johnny d]

אתה כנראה לא זוכר מהי רשימה מקושרת.

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

 

[vinney]

אבל גיל צודק

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

 

[gil levi]

זה עונה על השאלה אם הן נחתכות,

אבל צריך גם למצוא את החוליה המשותפת.

 

[johnny d]

אם זו הגדרת נחתכות אז זה לא בעיה.

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

 

[gil levi]

כנראה שזה הטריק-

להבין שנחתכות (במובן שיש להן חוליה משותפת) = מתלכדות.

 

[אמיתי ר]

בהחלט ניתן בזמן ליניארי

זו שאלה לא מסובכת מדי, ואף הייתה במבחן (או ממ"ן?) בקורס ממבני נתונים ומבוא לאלגוריתמים של באוניברסיטה הפתוחה. לשואלים לגבי הבהרה: הכוונה בשאלה יש שתי רשימות חד-כיווניות. בנקודה מסוימת יש להן איבר משותף, ומשם "והלאה" עד סוף הרשימות הן למעשה אותה רשימה. לדוגמה, אם האותיות הבאות מסמלות את הכתובת הממשית בזכרון אז: רשימה אחת: a-->b-->c-->d-->e-->f-->g ושניה: l-->m-->e-->f-->g ובמקרה זה, אנו מחפשים את התא e.

 

[johnny d]

עכשיו זה נשמע הגיוני יותר

ודיי קל למען האמת.

 

[Blue Beetle]

אפשרי בהחלט

ראשית סופרים את 2 הרשימות. נקרא להן A ו- B נניח ש-A היא הקצרה יותר. אז מקדמים את המצביע ל-A עד שמספר הצאצאים של המצביע ל-A שווה למספר האיברים ב-B. לצורך העניין a מצביע לאיברים שנשארו ב-A ו-b הוא ראש הרשימה B (כלומר b.next האיבר הראשון ברשימה). נשתמש במצביע נוסף c שבהתחלה (אחרי הספירה) יאותחל ל-a. כל עוד a.next=b.next נקדם אותם. אם a.next<>b.next אז c יקבל את a.next ואז נקדם אותם. כך נקדם את a ו-b עד סוף הרשימה. בסוף האלגורתים c יצביע על מקום החיתוך. ---------------------------------------------- עברתי במקרה, פורום נחמד יש לכם..