שאלת מבחן במבני נתונים - אוניברסיטת בר-אילן 2018 - סיבוכיות זמן

נתונים $m$ משתנים לא משורסכים $A_1, A_2, \ldots, A_m$ שכללם בטחום שלמים בתחום $[1, k]$. יחיא מ-$[1, k]$ הכמות הכוללת של אברים בכל המשתנים בחתחה. כמו אלגוריתמים שליהם פנימיים לפחות מחצית מהם שיוצאים אברים אחדים אתה אתה חד, הוקר כי בעל השמושופופוש בתיתן מופיסות כוללת $O(k+n)$.

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

פתרון: המטרה היא למצוא את כל המספרים השלמים בתחום $[1, k]$ המופיעים בלפחות $m/2$ מהמערכים הנתונים. נשתמש ב**מערך ספירה** כדי לפתור את הבעיה ביעילות. האלגוריתם המוצע הוא כדלקמן: 1. **יצירת מבני עזר:** ניצור מערך שלמים `counts` בגודל $k+1$ ונאתחל את כל תאיו ל-0. המערך `counts` ישמש לספירת מספר המערכים השונים שבהם מופיע כל איבר. כלומר, `counts[j]` יכיל את מספר המערכים שבהם המספר $j$ נמצא. בנוסף, ניצור מערך בוליאני `seen_in_current_array` בגודל $k+1$ ונאתחל את כל תאיו ל-`false`. מערך זה יעזור לנו לוודא שכל מספר ייספר פעם אחת בלבד עבור כל מערך $A_i$. 2. **מעבר על המערכים:** נעבור בלולאה על כל אחד מ-$m$ המערכים, $A_1, A_2, oils, A_m$. עבור כל מערך $A_i$: א. ניצור רשימה ריקה, `unique_elements_in_Ai`, שתכיל את האיברים הייחודיים שפגשנו במערך הנוכחי. ב. נעבור על כל איבר $x$ במערך $A_i$. עבור כל $x$ כזה, נבדוק את הערך `seen_in_current_array[x]`: i. אם `seen_in_current_array[x]` הוא `false`, זו הפעם הראשונה שאנו נתקלים במספר $x$ במערך $A_i$. לכן, נקדם את `counts[x]` ב-1, נשנה את `seen_in_current_array[x]` ל-`true`, ונוסיף את $x$ לרשימה `unique_elements_in_Ai`. ii. אם `seen_in_current_array[x]` הוא `true`, לא נעשה דבר, מכיוון שכבר ספרנו את הופעתו של $x$ במערך הנוכחי. ג. לאחר סיום המעבר על כל איברי $A_i$, נעבור על כל האיברים $y$ ברשימה `unique_elements_in_Ai` ונאפס את `seen_in_current_array[y]` בחזרה ל-`false`. שלב זה חיוני כדי להכין את מערך העזר `seen_in_current_array` לקראת עיבוד המערך הבא, $A_{i+1}$. 3. **איסוף התוצאות:** לאחר שסיימנו לעבד את כל $m$ המערכים, נעבור על המערך `counts` מאינדקס 1 עד $k$. ניצור רשימת תוצאות ריקה. לכל אינדקס $j$ שעבורו `counts[j] >= m/2`, נוסיף את $j$ לרשימת התוצאות. 4. **החזרת התוצאה:** נחזיר את רשימת התוצאות. **ניתוח סיבוכיות:** - **שלב 1 (אתחול):** יצירה ואתחול של שני מערכים בגודל $k+1$ לוקחת זמן של $O(k)$. - **שלב 2 (עיבוד המערכים):** הלולאה החיצונית רצה $m$ פעמים. הלולאה הפנימית (שלב 2.ב) עוברת על כל איבר בכל המערכים פעם אחת בדיוק. מכיוון שהמספר הכולל של האיברים בכל המערכים הוא $n$, סך הפעולות בשלב זה הוא פרופורציונלי ל-$n$. שלב האיפוס (2.ג) רץ רק על האיברים הייחודיים שהופיעו במערך הנוכחי. סך כל האיברים הייחודיים על פני כל המערכים (בצורה זו) לא יכול לעלות על $n$. לכן, הסיבוכיות הכוללת של שלב 2 היא $O(n)$. - **שלב 3 (איסוף התוצאות):** המעבר על המערך `counts` דורש $O(k)$ זמן. הסיבוכיות הכוללת של האלגוריתם היא הסכום של כל השלבים: $O(k) + O(n) + O(k) = O(n+k)$. $\blacksquare$