שאלה במבני-נתונים

[R i c h i e R i c h]

שאלה במבני-נתונים

מערך [A[1...n מכיל את כל השלמים מ-0 עד n חוץ מאחד. קל לקבוע מהו המספר החסר בזמן (O(n בעזרת מערך עזר [B[0..n, שבו רושמים את המספרים המופיעים ב- A. אולם בבעיה שלפנינו לא ניתן לגשת אל מספר המאוחסן ב- A באמצעות פעולה אחת. המספרים ב- A מיוצגים בכתיב בינארי, ופעולת הגישה היחידה המותרת היא "הבא את הסיבית ה-j של [A[i". פעולה זו מתבצעת בזמן קבוע. הראה שגם אם משתמשים אך ורק בפעולה זו כדי להשיג מידע מ- A, ניתן לקבוע מהו המספר החסר בזמן (O(n. טוב, אז ישבתי וחשבתי על פתרון יצירתי, בין השאר לסכום את הסיביות של ספרת האחדות/עשרות/וכולי ולהפחית את התוצאה מהסכום שהיה יוצא אילו כל המספרים היו נמצאים. רעיון נוסף היה להמיר כל מספר בינארי למספר שלם רגיל ולפתור כמו שהוצג בשאלה. הבעיה היא שככל שיש יותר מספרים במערך כך יש יותר סיביות בכל תא וזה כמובן משפיע על זמן הריצה....(או שלא?) למישהו יש רעיון?

 

[עדין ר]

...

לצורך הפשטות, נניח ש-n הוא חזקה של 2. (אם לא, אפשר להשלים את A עד החזקה הקרובה של 2, ובכך n מוכפל לכל היותר) נחזיק רשימה מקושרת שמאותחלת להכיל את המספרים מ-1 עד n. נעבור על הביט הראשון (הפחות משמעותי) של כל המספרים ב-A שהאינדקס שלהם נמצא ברשימה שלנו, ונמצא איזה ביט מופיע פחות. נסמן ביט זה ב-b. זהו הביט הראשון של המספר החסר. כעת נעבור על הרשימה שלנו, ונמחק ממנה את האינדקסים של האיברים ב-A שהביט הראשון שלהם שונה מ-b. כעת ברשימה יש n/2 איברים. נחזור על הפעולה הנ"ל עם הביט השני, השלישי וכו' כאשר בכל פעם אנחנו עוברים על חצי מהאיברים שעברנו עליהם בפעם הקודמת, וכך יצא שמספר הפעולות הוא

2 * n + 2 * (n/2) + 2 * (n/4) + ... + 2 * 1 = O​