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

האלגוריתם select שנלמד בתרגיל מקבל כקלט מערך לא ממוין בגודל $n$, ומספר $i$ בטווח $1$ עד $n$, ומחזיר את האיבר ה-$i$ בגודלו במערך. באלגוריתם חילקנו את המערך ל $n/5$ קבוצות בנות $5$ איברים בכל קבוצה. בשאלה זו, אנו מתבוננים בשינוי קל שנעשה באלגוריתם – במקום לחלק את המערך ל $n/5$ קבוצות, נחלקו ל $n/3$ קבוצות, כאשר כל קבוצה מכילה $3$ איברים. א( כמה איברים (לפחות) מצליח לנפות "חציון החציונים" לאחר השינוי? ב( תאר/י נוסחא לזמן הריצה של האלגוריתם, ופתור/פתרי אותה. האם השינוי משנה את זמן הריצה של האלגוריתם? (שימו לב – כפי שניתחנו בכיתה, הנוסחא אינה מדויקת, אלא היא הערכה בלבד).

רמז: בחנו כיצד שינוי גודל הקבוצות מ-5 ל-3 משפיע על מספר האיברים שניתן להבטיח שהם קטנים או גדולים מאיבר הציר ("חציון החציונים"). מכאן, גזרו את נוסחת הנסיגה החדשה.

פתרון: ### סעיף א: מספר האיברים המנופים האלגוריתם המשונן מחלק את המערך של $n$ איברים ל-$\frac{n}{3}$ קבוצות של 3 איברים כל אחת (נניח לשם פשטות ש-$n$ מתחלק ב-3). לאחר מכן, הוא מוצא את החציון של כל קבוצה, ואז קורא לעצמו רקורסיבית כדי למצוא את חציון החציונים, שנקרא לו $p$. המטרה שלנו היא למצוא חסם תחתון למספר האיברים שגדולים מ-$p$ וחסם תחתון למספר האיברים שקטנים מ-$p$. זה ייתן לנו חסם על גודל תת-הבעיה הרקורסיבית הבאה. - ישנן $\frac{n}{3}$ קבוצות, ולכן $\frac{n}{3}$ חציונים. - איבר הציר $p$ הוא החציון של $\frac{n}{3}$ החציונים הללו. - לכן, לפחות מחצית מהחציונים קטנים או שווים ל-$p$. מספרם הוא לפחות $\frac{1}{2} \cdot \frac{n}{3} = \frac{n}{6}$. - כל חציון כזה, בקבוצה המקורית שלו בת 3 איברים, גדול או שווה לפחות מאיבר אחד נוסף. לכן, כל קבוצה כזו תורמת לפחות 2 איברים שקטנים או שווים ל-$p$. - בסך הכל, מספר האיברים שקטנים או שווים ל-$p$ הוא לפחות $2 \cdot \frac{n}{6} = \frac{n}{3}$. באופן סימטרי, מספר האיברים שגדולים או שווים ל-$p$ הוא גם לפחות $\frac{n}{3}$. בשלב הרקורסיבי הבא, לאחר החלוקה (partition) סביב $p$, נמשיך לחפש באחת משתי הקבוצות (הקטנים מ-$p$ או הגדולים מ-$p$). במקרה הגרוע ביותר, נצטרך לחפש בקבוצה הגדולה יותר. מכיוון שהצלחנו להראות שקיימים לפחות $\frac{n}{3}$ איברים בכל צד של $p$, אנו יכולים להבטיח שנפטרנו (ניפינו) לפחות מהקבוצה הקטנה יותר, שגודלה הוא $\frac{n}{3}$ איברים. לכן, האלגוריתם מצליח לנפות **לפחות $\frac{n}{3}$ איברים** בכל קריאה רקורסיבית. $\blacksquare$ ### סעיף ב: נוסחת נסיגה וזמן ריצה זמן הריצה של האלגוריתם, $T(n)$, מורכב מהשלבים הבאים: 1. **חלוקה לקבוצות ומציאת חציונים:** חלוקת המערך ל-$\frac{n}{3}$ קבוצות וחישוב חציון של כל קבוצה (פעולה שלוקחת זמן קבוע $O(1)$ לכל קבוצה של 3) לוקח זמן לינארי, $O(n)$. 2. **קריאה רקורסיבית למציאת חציון החציונים:** קריאה רקורסיבית על מערך החציונים, שגודלו $\frac{n}{3}$. שלב זה לוקח $T(\frac{n}{3})$. 3. **חלוקת המערך המקורי:** ביצוע Partition סביב איבר הציר $p$ לוקח זמן לינארי, $O(n)$. 4. **קריאה רקורסיבית על תת-מערך:** במקרה הגרוע ביותר, כפי שראינו בסעיף א', נצטרך להמשיך לחפש בקבוצה הגדולה יותר. גודלה של קבוצה זו הוא לכל היותר $n - \frac{n}{3} = \frac{2n}{3}$. שלב זה לוקח $T(\frac{2n}{3})$. לפיכך, **נוסחת הנסיגה** לזמן הריצה היא: $T(n) \le T(\frac{n}{3}) + T(\frac{2n}{3}) + O(n)$ כדי לפתור נוסחה זו, נשים לב שסכום גדלי הבעיות הרקורסיביות הוא $\frac{n}{3} + \frac{2n}{3} = n$. במקרים כאלה, זמן הריצה אינו לינארי. ניתן לראות זאת באמצעות עץ הרקורסיה: בכל רמה בעץ, סך העבודה (החלק הלינארי) הוא $O(n)$. עומק העץ נשלט על ידי הענף הארוך ביותר, $T(\frac{2n}{3})$, ולכן עומק העץ הוא $O(\log_{\frac{3}{2}} n) = O(\log n)$. סך העבודה הוא העבודה בכל רמה כפול מספר הרמות, כלומר $O(n \log n)$. **השוואה ושינוי בזמן הריצה:** - באלגוריתם select המקורי (עם קבוצות של 5), נוסחת הנסיגה הייתה $T(n) \le T(\frac{n}{5}) + T(\frac{7n}{10}) + O(n)$. מכיוון ש- $\frac{1}{5} + \frac{7}{10} = \frac{9}{10} < 1$, סך העבודה בכל רמה של עץ הרקורסיה יורד גיאומטרית, והפתרון הוא **$O(n)$**. - באלגוריתם המשונן (עם קבוצות של 3), הפתרון הוא **$O(n \log n)$**. **מסקנה:** כן, השינוי משנה את זמן הריצה של האלגוריתם. הוא הופך אותו מלינארי, $O(n)$, ללינארי-לוגריתמי, $O(n \log n)$, מה שהופך אותו לא יעיל יותר מאשר פשוט למיין את המערך כולו ($O(n \log n)$) ולבחור את האיבר ה-$i$. $\blacksquare$