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

פרק זה לוקה בחסר. אתם מוזמנים לתרום לוויקיספר ולהשלים אותו. ראו פירוט בדף השיחה.

א

ראשית נמיין את ‪ A‬בעזרת אלגוריתם מיון הרץ בזמן )‪ . O(n log n‬בפרט ניתן להשתמש ב‬מיון מיזוג. לאחר המיון, המופעים של כל מספר מופיעים ברצף. בפרט, אם יש איבר רוב אזי הוא‬ ‫מופיע ממקום ‪ $\displaystyle i$ ‬ועד מקום ‪ $\displaystyle j$ ‬ כאשר ‪  \left\lfloor n / 2 \rightt\rfloor‬ ואם אין איבר רוב אזי מספר המופעים של כל‬ ‫איבר הוא לכל היותר ‪ .n/2‬בנקודה זו ישנן מספר אופציות:‬

נרוץ על אברי המערך לפי הסדר ונספור הופעות רצופות של כל איבר. אם מספר ההופעות‬ ‫הרצופות של איבר כלשהו הוא לפחות 1+ ‪ -n/2‬אז הוא איבר הרוב. אחרת, אין איבר כזה.‬
נרוץ על ‪ i‬מ 1 ועד )לכל היותר( ‪ , n  n / 2  n / 2‬ונבדוק אם ]‪ . A[i ]  A[i  n / 2‬אם‬ ‫מצאנו כזה ‪ i‬אז נחזיר את ] ‪) A[i‬אחרת נחזיר שאין איבר רוב(.‬
נשים לב כי לאחר מיון המערך, אם יש בו איבר רוב אזי הוא בהכרח נמצא במקום 1+ ‪ .n/2‬נימוק :‬

                     ‫האינדקס הראשון של איבר הרוב חייב להתחיל ב ‪ i‬כך ש מצד אחד 1 ‪ i ‬ומצד שני‬
 ‫1 ‪ i  n  n / 2  n / 2  n / 2 ‬ולכן תמיד מתקיים: ‪ . i  n / 2  1  i  n / 2‬מספיק‬
   ‫אם כן לבדוק האם ]1 ‪ A[ n / 2 ‬מופיע לפחות 1+ ‪ n/2‬פעמים וזאת ע"י ספירת האיברים השווים‬
                                                        ‫לאיבר זה והנמצאים משמאלו או מימינו במערך.‬
     ‫זמן הריצה בכל מקרה: זמן הריצה של אלגוריתם המיון ועוד לולאה העוברת על כל איבר במערך לכל‬
                                              ‫היותר פעם אחת - )‪. (n log n)  (n)  (n log n‬‬
                                                           ‫להלן הפסאודו קוד עבור האופציה הראשונה.‬

‫)‪Maj(n,A‬‬

  ‫/* ‪Merge-Sort(A) /* Sort the elements of A‬‬
  ‫/* ‪j1; xA[1]; count 1 /* x is the current candidate for the majority element‬‬
 ‫{ ) ‪while (j < n and count n/2‬‬
      ‫;++‪j‬‬
      ‫1+‪if (A[j]=x) count  count‬‬
                              ‫‪/* if the next element is the same as the candidate‬‬
                                    ‫/* ‪(previous element) then increase count‬‬
     ‫{ ‪else‬‬
         ‫;]‪x  A[j‬‬             ‫/* ‪/* change candidate to new element and initialize count‬‬
         ‫1 ‪count ‬‬
     ‫}‬
  ‫)‪if (count > n/2) return(x‬‬
  ‫)‪else return(No-Majority-Element‬‬
 ‫}‬

ב

האלגוריתם ראשית קורא ל ‪ , Candidate‬המחזירה לו "מועמד" ‪ .x‬לאחר מכן עובר האלגוריתם על‬ ‫איברי המערך ‪ A‬וסופר כמה פעמים הופיע ‪ .x‬אם מספר זה הוא לפחות 1 ‪ n / 2 ‬אזי הוא מחזיר אותו,‬

     ‫ואחרת הוא מחזיר שאין איבר רוב. לפי ההנחה על ‪ ,Candidate‬אם יש במערך איבר רוב אזי השגרה‬
               ‫מחזירה אותו, ובמצב זה האלגוריתם יחזיר אותו. אם אין איבר רוב אזי לא משנה מה מחזירה‬
   ‫‪ ,Candidate‬האיבר המוחזר יופיע לכל היותר ‪ n / 2‬פעמים ולכן האלגוריתם יחזיר שאין איבר רוב,‬
   ‫כנדרש. זמן הריצה הוא פשוט הסכום של זמן הריצה של ‪ ,Candidate‬והלולאה שעוברת פעם אחת על‬
                                                                             ‫‪ ,A‬כלומר )‪.T(n)+O(n‬‬

‫)‪Maj(A,n‬‬

  ‫/* ‪x  Candidate(A,n) /* x is the candidate for being a majority element‬‬
 ‫0 ‪count ‬‬
 ‫)‪for (j=1 to n‬‬             ‫/* ‪/* count number of appearances of x in A‬‬
    ‫‪if (A[j]==x) then‬‬
       ‫1+‪count  count‬‬
 ‫/* ‪if(count n/2 +1) then return(x) /* x is the majority element‬‬
 ‫)‪else return(NO-MAJORITY-ELEMENT‬‬
       ‫‪n  2‬‬        ‫‪n ‬‬

ג

ראשית נשים לב כי ‪ y‬הוא איבר רוב ב ‪ B‬אם ורק אם הוא מופיע לפחות ‪ 1   ‬‬

       ‫‪ 2 ‬‬          ‫‪2‬‬
       ‫‪‬‬      ‫‪‬‬
     ‫פעמים ב ‪ .B‬יהי ‪ x‬איבר הרוב ב ‪ .A‬ישנם שלושה מקרים: )1( גם ‪ A[i] ≠ x‬וגם ‪(2) ;A[j] ≠ x‬‬
   ‫‪ A[i]=x‬ו ‪ A[i] ≠ x (3) ; A[j]x‬ו ‪ ;A[j]=x‬במקרה הראשון, מספר המופעים של ‪ x‬ב ‪ B‬שווה‬
    ‫לזה שב ‪ ,A‬כלומר הוא לפחות 1+ ‪ n/2‬שזה יותר מ ‪ , n/2‬ולכן הוא איבר רוב של ‪ .B‬במקרה‬
   ‫השני והשלישי, מספר המופעים של ‪ x‬ב ‪ B‬הוא אחד פחות מאשר ב ‪ ,A‬כלומר לפחות ‪ ,n/2‬ולכן גם‬
                                                                  ‫במקרה זה הוא איבר רוב של ‪.B‬‬
                                                                                              ‫ד.‬

‫)1(. )מספיק היה לתת הסבר מילולי פחות פורמאלי מזה שיוצג לעיל(. נוכיח באינדוקציה על ‪ j‬כי הטענה‬

   ‫מתקיימת לכל ‪ j‬בנקודה בה נבדקים תנאי ה ‪) while‬ולכן בפרט תתקיים כאשר אחד מהם לפחות מופר‬
       ‫ויוצאים לכן מהלולאה(. הבסיס: 1=‪) j‬לפני האיטרציה הראשונה(. במצב זה ‪ , k-j+1=k‬כלומר תת‬
‫המערך מכיל רק את ‪ ,A[k]=val‬ואכן באיתחול 1=‪ count‬כנדרש. צעד האינדוקציה: נניח מתקיים עבור‬
‫1-‪ j‬נוכיח עבור ‪ . j‬לפי הנחת האינדוקציה, בתחילת האיטרציה הקודמת )כאשר הערך של ‪ j‬היה קטן ב‬
   ‫1(, ‪ count‬היה מספר ההופעות של הערך ‪ val‬בתת המערך ]‪ A[k-j+2,...,k‬פחות מספר ההופעות של‬
   ‫ערכים אחרים באותו תת מערך. במהלך האיטרציה, אם ‪ A[k-j+1]=val‬אז הערך של ‪ count‬גדל ב 1‬
    ‫)ואכן ההפרש גדל ב 1( ואחרת הוא קטן ב 1 )ואכן ההפרש קטן ב 1(. מכאן שצעד האינדוקציה תקף.‬
 ‫)2(. כיוון שבתחילת כל איטרציה של לולאת ה ‪ ,while‬נבדק ש 0>‪ count‬ו‪ count‬קטן לכל היותר ב 1‬
‫בכל איטרציה, הרי שכאשר יוצאים מלולאת ‪ , while‬או ש 0>‪ count‬או ש 0=‪ .count‬במקרה הראשון,‬
     ‫לפי תת-הסעיף הקודם, מספר הפעמים ש ‪ val‬מופיע ב ]‪ A[1,...,k‬גדול ממספר הפעמים שמופיע כל‬
  ‫איבר אחר, כלומר, ‪ val‬הוא איבר הרוב בתת המערך הזה. במקרה השני מספר הפעמים ש ‪ val‬מופיע ב‬
        ‫]‪ A[1,...,k‬שווה למספר הפעמים שמופיע איבר אחר. מכאן שכל איבר מופיע לכל היותר מחצית‬
                                                             ‫הפעמים, ומכאן נובע שאין איבר רוב.‬
     ‫)3(. נפעל לפי ההדרכה. בסיס האינדוקציה, 1=‪ .k‬במקרה זה יש בתת המערך איבר יחיד והוא איבר‬
                                                    ‫הרוב. השגרה אכן מחזירה איבר זה בשורה 3.‬
     ‫צעד האינדוקציה: נניח כי טענת האינדוקציה מתקיימת לכל ‪) 0<t<k ,t‬כלומר, אם ]‪ A[1,...,t‬מכיל‬
      ‫איבר רוב אז )‪ Candidate(A,t‬תחזיר אותו( ונוכיח עבור ‪ .k‬לפי תנאי הסיום של לולאת ה ‪,while‬‬
   ‫ומכיוון ש ‪ j‬גדל ב 1 בכל איטרציה, ו ‪ count‬גדל ב 1 או קטן ב 1 בכל איטרציה, הרי שהשגרה יוצאת‬

‫מלולאת ה ‪ while‬או כאשר ‪ j==k‬או כאשר 0==‪) count‬או ששניהם מתקיימים(. נתבונן בשני המקרים.‬

  ‫אם ‪ j==k‬אזי לפי סעיף ד)2(, אם יש ב ]‪ A[1,...,k‬איבר רוב אזי הוא יוחזר וצעד האינדוקציה מתקיים‬

‫)ללא צורך בשימוש בהנחת האינדוקציה(. אחרת, 0==‪ .count‬לפי סעיף ד)1( זה אומר שמספר המופעים‬

  ‫של ‪ val‬זהה למספר המופעים של איברים השונים ממנו. אם נחשוב עליהם כמחולקים לזוגות, )‪(val,z‬‬

‫כאשר ‪ ,zval‬הרי לפי סעיף ג, אם יש ב ]‪ A[1,...,k‬איבר רוב אזי הוא גם איבר הרוב של ]‪.A[1,...,k-j‬‬ ‫כיוון ש 2‪ , j‬הרי ‪ k-j<k‬ולפי הנחת האינדוקציה, הקריאה ל )‪ Candidate(A,k-j‬תחזיר את איבר הרוב‬

                                                                         ‫של ]‪ A[1,...,k-j‬כנדרש.‬
                          ‫כיוון שהוכחנו שהטענה מתקיימת לכל ‪ k‬הרי בפרט היא מתקיימת עבור ‪.k=n‬‬