שאלת מבחן במבוא למדעי המחשב - אוניברסיטת תל אביב 2021 - רקורסיה

בהינתן רשימה $L$ באורך $n$, נגדיר **איבר רוב** ברשימה להיות איבר אשר מופיע יותר מ-$n/2$ פעמים ברשימה (אם קיים). לאורך שאלה זו נניח כי איברי הרשימה ניתנים להשוואה (כלומר, בהינתן שני איברים $a, b$ מהרשימה, ניתן לבדוק האם $a == b$), אך אין עליהם יחס סדר (כלומר, לא ניתן לבדוק האם $a < b$ או $a > b$). כמוכן, ניתנת לנו אפשרות ההשוואה בין איברים ברשימה (בפייתון: $a == b$) מתבצעת בזמן קבוע. לדוגמה, ברשימה $L = [1, "a", "a", 1, 1]$ האיבר $1$ הוא איבר רוב וברשימה $L = [1, "a", 1, "b"]$ אין איבר רוב. לאורך שאלה זו נעסוק באלגוריתמים דטרמיניסטיים (כלומר לא אקראיים) בלבד. בפרט, אין להשתמש ב-hashing. **בשאלה כולה** (הן במימוש עצמי הן במימוש מובנה כמו dict או set). בנוסף, ניתן להניח כי $None$ אינו איבר ברשימה. **א.** ממשו את הפונקציה $maj$ המקבלת כקלט רשימה $L$ ומחזירה כפלט איבר רוב ברשימה, אם קיים, $None$ אחרת. **הנחיות:** * על הפתרון להיות **רקורסיבי**. * ניתן להשתמש ב-$maj$ כפונקציה מעטפת. * על הפתרון לרוץ בסיבוכיות זמן $O(n \log n)$. **דוגמאות הרצה:** ```python >>> maj([1, "a", "a", 1, 1]) == 1 True >>> maj([1, "a", 1, "b"]) == None True ``` **ב.** ציירו את עץ הרקורסיה של הפונקציה $maj$ שלכם עבור הקלט $L = [\alpha, \alpha, \beta, \alpha, \beta, \delta, \alpha, \alpha, \alpha]$, כאשר $\alpha, \beta, \delta$ איברים כלשהם. יש לרשום מימין לכל צומת ביצע את הקלט ואת הפלט שאותו החזיר. **ג.** נמקו מדוע זמן הריצה של הפונקציה $maj$ שלכם הוא אכן $O(n \log n)$ כנדרש.

רמז: **א.** חלוקה לשניים, מציאת מועמד רקורסיבית בכל חצי, ואם המועמדים שונים — ספירה ליניארית של כל מועמד ברשימה המלאה. **ג.** $\log n$ רמות × $O(n)$ עבודה ברמה = $O(n \log n)$.

פתרון: **א — maj.** הרעיון: **Divide and Conquer**. מחלקים את הרשימה לשני חצאים, מוצאים את **מועמד לרוב** בכל חצי רקורסיבית. אם שני החצאים מחזירים אותו מועמד — הוא המועמד. אם הם מחזירים מועמדים שונים — סופרים את מספר ההופעות של כל מועמד ברשימה השלמה ובודקים מי (אם בכלל) הוא רוב. ```python def maj(L): if len(L) == 1: return L[0] if len(L) == 2 and L[0] != L[1]: return None max1 = maj(L[:len(L)//2]) max2 = maj(L[len(L)//2:]) if max1 == max2: return max1 cnt1 = cnt2 = 0 for i in L: if i == max1: cnt1 += 1 if i == max2: cnt2 += 1 if cnt1 == cnt2: return None if cnt1 > len(L) // 2: return max1 elif cnt2 > len(L) // 2: return max2 return None ``` **ב — עץ הרקורסיה.** הקלט $[\alpha, \alpha, \beta, \alpha, \beta, \delta, \alpha, \alpha, \alpha]$ (אורך 9). מחלקים ל-$[\alpha, \alpha, \beta, \alpha]$ ו-$[\beta, \delta, \alpha, \alpha, \alpha]$. ממשיכים רקורסיבית. בסופו של דבר, שני החצאים יחזירו $\alpha$ (כי $\alpha$ הוא רוב בשני החצאים). *(הסטודנט צייר את העץ המלא בכתב יד.)* **ג — הוכחת $O(n \log n)$.** עומק הרקורסיה הוא $\log n$ (כי בכל קריאה מחלקים את הרשימה לשני חצאים). בכל קריאה, אם המועמדים שונים, נעשית ספירה ליניארית ($O(n)$) על הרשימה הנוכחית. בנוסף, ה-slicing ($L[:n//2]$) עולה $O(n)$. בכל **רמה** של הרקורסיה, סכום אורכי הרשימות הוא $n$ (כי הרשימות לא חופפות). לכן סכום העבודה ברמה הוא $O(n)$. יש $\log n$ רמות. סך הכול: **$O(n \log n)$.** $\blacksquare$