מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/מיון הכנסה ומיזוג/תרגילים/מציאת איבר הרוב במערך/שאלה

יהי A מערך שבו $\displaystyle n$ מספרים שלמים. מספר $\displaystyle x$ יקרא איבר רוב של A אם מספר ההופעות של $\displaystyle x$ ב-A הוא לפחות $\displaystyle \left\lfloor {\frac {n}{2}}\right\rfloor +1$.

דוגמה: אם $\displaystyle n=7$ ו-A = [1, 5, 2, 5, 5, 14, 5], אז 5 הוא איבר רוב, כי הוא מופיע לפחות $\displaystyle \left\lfloor {\frac {7}{2}}\right\rfloor +1=4$ פעמים.

שימו לב כי אם קיים איבר רוב במערך A אזי הוא יחיד.

נגדיר בעיה שנקרא לה "בעיית איבר הרוב": בהינתן המערך A וגודלו $\displaystyle n$, יש למצוא האם יש בA איבר רוב. אם כן יש להדפיס איבר זה; אחרת, יש להדפיס שלא קיים איבר רוב.

בסעיפים הבאים נעסוק בבעיית איבר הרוב.

א'

אנא כתוב פסוודו-קוד עבור אלגוריתם לפתרון בעיית איבר הרוב הרץ בזמן $\displaystyle \Theta (n\cdot \log(n))$. אנא הסבר בקיצור מה עושה האלגוריתם, מדוע הוא פותר את בעיית איבר הרוב, ונתח את זמן הריצה שלו.

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

ב'

הניחו שברשותכם שגרה בשם Candidate(A,n) שמקבלת את המערך A וגודלו $\displaystyle n$. אם בA יש איבר רוב, אז השגרה מחזירה את איבר הרוב. אחרת, השגרה מחזירה איבר כלשהוא מאיברי A. נקרא לזמן הריצה של Candidate(A,n) (כלומר, על קלט באורך $\displaystyle n$)‏ $\displaystyle T(n)$.

אנא כתבו פסוודו-קוד עבור אלגוריתם שפותר את בעיית איבר הרוב בזמן $\displaystyle T(n)+O(n)$ על ידי שימוש בשגרה Candidate. הסבירו את נכונותו ואת זמן הריצה שלו.

שימו לב: אינכם צריכים לכתוב את השגרה Candidate עצמה, אלא רק אלגוריתם שמשתמש בשגרה.

ג'

יהיו $\displaystyle i,j$ שני אינדקסים כך ש A[i] != A[j]. יהי B מערך המכיל $\displaystyle n-2$ איברים שהם כל איברי A מלבד A[i] ו]A[j

דוגמה: עבור: A=[1,5,2,5,5,14,5] $\displaystyle i=1$ $\displaystyle j=2$ יש לנו B=[2,5,5,14,5].

אנא הוכיחו את הטענה הבאה: אם בA יש איבר רוב $\displaystyle x$, אז $\displaystyle x$ הוא גם איבר רוב בB.

ד'

נתונה השגרה הבאה, בשם Candidate , המקבלת מערך A ומספר שלם $\displaystyle k$ בתחום $\displaystyle 1\leq k\leq n$, ומחזירה מספר.

Candidate(A, k)
1	if  k = 1 
2		return A[1] 
3	val = A[k] 
4	j  = 1;  count = 1
5	while( j < k and count > 0 )
6		if   ( A[k-j] = val ) then 
7			++count
8		else
9			--count
10			++j
14	if  j  == k 
15		return val
16	else
17		return Candidate(A ,k - j)

אנא הראה כי אם בA יש איבר רוב, אזי (Candidate(A, n תחזיר אותו; כמו כן, אנא נתח את סיבוכיות הפונקציה.