שאלת מבחן במבני נתונים ומבוא לאלגוריתמים - האוניברסיטה הפתוחה 2020 - אלגוריתמים

נתונים מערך $A[1..n]$ של מספרים ממשיים ומספר טבעי $m$ המקיים $2m < n$. כתבו אלגוריתם הבודק האם קיים ב-$A$ איבר $z$ המקיים את שני התנאים הבאים: (1) $A$ מכיל לפחות $n - 2m$ איברים קטנים מ-$z$; (2) $z$ מופיע יותר מ-$m$ פעמים ב-$A$. זמן הריצה הנדרש של האלגוריתם הינו $\Theta(n)$. רמז: חשבו כיצד סעיף א' עשוי לעזור. שימו לב ש-$z$ הוא לא חלק מהקלט.

רמז: מצאו את האיבר ה-$(n-2m)$ בגודלו בזמן $O(n)$ (באמצעות SELECT). כל האיברים מעליו מהווים תת-מערך בגודל $2m$. חפשו בתת-מערך זה איבר שמופיע יותר מ-$m$ פעמים — זה בדיוק בעיית majority על מערך בגודל $\le 2m$!

פתרון: **רעיון:** תנאי (1) דורש ש-$z$ גדול מלפחות $n-2m$ איברים, כלומר $z$ נמצא בין $2m$ האיברים הגדולים ביותר. תנאי (2) דורש ש-$z$ מופיע יותר מ-$m$ פעמים — כלומר יותר ממחצית מתוך $2m$ האיברים הגדולים. **האלגוריתם:** **שלב 1:** מצאו את האיבר ה-$(n-2m+1)$ בגודלו (ה-order statistic) באמצעות אלגוריתם SELECT בזמן $\Theta(n)$. נסמנו $p$. **שלב 2:** צרו מערך $B$ המכיל את כל האיברים ב-$A$ שגדולים או שווים ל-$p$. גודלו $\le 2m$ (ואולי קצת יותר אם יש שוויונות, אבל ניתן לטפל בכך). זמן: $O(n)$. **שלב 3:** הפעילו את אלגוריתם Boyer-Moore (מסעיף א') על $B$ כדי לבדוק האם קיים איבר $z$ המופיע יותר מ-$|B|/2 \ge m$ פעמים ב-$B$. זמן: $O(m) = O(n)$. **שלב 4:** אם נמצא כזה $z$, ודאו שהוא מופיע יותר מ-$m$ פעמים ב-$A$ (ספירה בזמן $O(n)$) ושיש לפחות $n-2m$ איברים קטנים ממנו. **סיבוכיות:** כל שלב $O(n)$, סה"כ $\Theta(n)$.