חידה שנשאלתי,

[Zack DA]

../images/Emo41.gif חידה שנשאלתי,

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

O​

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

O(1)​

בהצלחה !

 

[IP yuval]

כל המספרים עד n חייבים להיות שם (אז

זה קל) או שיכולים להיות מספר מספרים אשר מופיעים מספר פעמים (זה מה שכתבת)?

 

[Zack DA]

לא כולם חייבים להיות שם,

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

 

[codec]

ממויין או לא ?

אני אניח שלא ממויין, עד שיוכח אחרת.

 

[Zack DA]

מן הסתם לא ממויין.....

 

[yoash17]

אני מניח שכל מספר מופיע פעם אחת ואז

אפשר פשוט לסכום את כל המספרים ואת הסכום לחסר מסכום סדרה חשבונית שהאיבר הראשון שלה הוא 0 ויש בה n+1 איברים שהיפרש בין איבר לאיבר הוא 1 בהצלחה.

 

[ahab]

מאיפה ההנחה בדיוק?

Zack אמר במפורש שלא מובטח כי כל המספרים מופיעים שם. תקרא את כל השרשור לפני שאתה עונה... אבל אם מותר להניח הנחות, אני אניח כי המספר 2 מופיע יותר מפעם אחת, ואתן אלגוריתם שרץ בזמן O של 1

 

[BMWE]

שאלה נוספת על אותו בסיס

יש מערך בגודל n, המכיל מספרים שלמים מ 0 עד n פרט למספר בודד. אפשר למצוא את המספר בסיבוכיות O, ע"י שימוש במערך נוסף בגודל n+1. הבעיה שלא ניתן לגשת למספר עצמו, אלא, רק לביטים של המספר. כלומר לביט i של המספר j. צריך להראות שגם אם משתמשים בשיטה של גישה לביטים, ניתן לקבוע את המספר החזר ע"י O.

 

[DNile]

חשב מראש,

את הערך של:

X = 1 XOR 2 XOR 3 XOR 4 XOR 5 XOR 6 .. XOR n​

לערך מכן, תקסור את המספר שקיבלת X, עם עם כל ביט, של כל מספר. ז"א: X = X XOR (bitiofj ShiftedLeftby i)

 

[BMWE]

זה עדיין לא מסתדר לי

עבור חישוב X, זה זמן n. עבור גישה לכ"א מהביטים של מספר בודד זה log, ולכל המספרים יחדיו זה nlogn. את כיוון האלגו' הבנתי, אך לא הבנתי את הפתרון שלו

 

[DNile]

למה גישה לכ"א מהביטים זה logn?

יש לך n מספרים? לכל מספר יש m ביטים? m זה קבוע, שנקבע לפי גודל כל איבר במערך? סה"כ יש לך m*n ביטים, ולרוץ על כל ביט בנפרד, זה O.

 

[BMWE]

n מספרים

מה זה n? n לא ידוע מראש ויכול לגדול. לכן מספר הביטים הוא logn.

 

[DNile]

מאחר ובפתרון שלך

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

 

[אלוהים1980]

יש לי רעיון...

להשתמש באלגוריתם למציאת חציון. הסיבוכיות שלו היא O של N. לדוגמה, נניח שהמערך הוא בגודל 10, והמספרים בטווח 1-9, וגילינו שהחציון הוא 3. זה אפשרי אם המספרים הם 1,1,2,2,3,4,4,7,8 לדוגמה (לא ממויינים) לאחר שנצאנו את החציון, נחלק את את המערך לשני חלקים - אלו שגדולים מהחציון ואלו שקטנים מהחציון - שוב פעם O של N. נבדוק האם יש יותר ממופע אחד של החציון - O של N - אם כן, סיימנו. אם לא נמשיך באופן הבא: אם החציון גדול מ N חלקי 2 נסתכל על החלק של הגדולים מהחציון ונפעיל שוב את האלגוריתם, אלא שהפעם הטווח הוא מהחציון ועד N , ואחרת נסתכל על החלק של הקטנים מהחציון והטווח הוא מ 1 ועד החציון. בדוגמה - נסתכל על החלק הכולל את 1,1,2,2,3 נראה לי שזה יפתור את הבעיה. מה אתם אומרים? הסיבוכיות של כל שלב תהיה כאורך המערך של אותו השלב. זאת אומרת - N ועוד N חלקי 2 ועוד N חלקי ארבעה ועוד N חלקי שמונה וכן הלאה. סה"כ זה יוצא O של N.

 

[אלוהים1980]

אגב,

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

 

[IsraeliSecretToilets]

אממ..

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

 

[אלוהים1980]

בעסה...