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

שאלה 2 – תכנון דינאמי (תת-סדרה עולה מרבית) נתונה סדרה של $n$ מספרים שלמים $s = (x_1, \ldots, x_n)$ שונים זה מזה. תת-סדרה של $s$ הינה סדרה מהצורה $(x_{i_1}, x_{i_2}, \ldots, x_{i_k})$ שבה $1 \leq i_1 < i_2 < \ldots < i_k \leq n$, וסדר האיברים בתת-הסדרה זהה לסדר שלהם ב-$s$. תת סדרה נקראת עולה אם $x_{i_1} < x_{i_2} < \ldots < x_{i_k}$. הציגו אלגוריתם למציאת תת-סדרה עולה שאורכה מרבי. בניתוח זמן הריצה הניחו, שכל פעולה אלמנטרית על מספרים (כמו חיבור, חיסור או השוואה) מתבצעת בזמן $\Theta(1)$. ניקוד: אלגוריתם שרץ בזמן ריבועי $\Theta(n^2)$ מקנה 19 נקודות. אלגוריתם משופר שרץ בזמן $\Theta(n \log n)$ מקנה 33 נקודות.

רמז: בפתרון הריבועי, הגדירו לכל אינדקס $i$ את אורך תת-הסדרה העולה הארוכה ביותר המסתיימת באיבר $x_i$. לפתרון היעיל יותר, חשבו כיצד לשמור מערך ממוין של האיברים הקטנים ביותר האפשריים עבור כל אורך של תת-סדרה, ולעדכן אותו באמצעות חיפוש בינארי.

פתרון: בעיית מציאת תת-סדרה עולה מרבית היא בעיה קלאסית הנפתרת באמצעות **תכנות דינמי**. נציג שני פתרונות, הראשון בסיבוכיות $\Theta(n^2)$ והשני בסיבוכיות $\Theta(n \log n)$. ### פתרון בסיבוכיות $\Theta(n^2)$ **הגדרת תת-בעיה:** נגדיר מערך `dp` בגודל $n$. עבור כל אינדקס $i$ (מ-$1$ עד $n$), `dp[i]` יכיל את אורכה של תת-הסדרה העולה הארוכה ביותר המסתיימת באיבר $x_i$. **נוסחת הנסיגה (רקורסיה):** כדי לחשב את `dp[i]`, עלינו למצוא איבר קודם $x_j$ (כלומר, $j < i$) שקטן מ-$x_i$ ($x_j < x_i$), ושנותן את תת-הסדרה העולה הארוכה ביותר שניתן להרחיב באמצעות $x_i$. אם נמצא $j$ כזה, הרי שאורך תת-הסדרה החדשה המסתיימת ב-$x_i$ יהיה `dp[j] + 1`. אנו נרצה לבחור את ה-$j$ שממקסם ערך זה. אם לא קיים $j$ כזה, פירוש הדבר ש-$x_i$ הוא האיבר הקטן ביותר עד כה, ולכן הוא פותח תת-סדרה חדשה באורך 1. לפיכך, נוסחת הנסיגה היא: $dp[i] = 1 + \max \{ dp[j] \mid 1 \le j < i \text{ and } x_j < x_i \}$ כאשר המקסימום על קבוצה ריקה מוגדר כ-0. **אלגוריתם:** 1. אתחל מערך `dp` בגודל $n$, כאשר כל תאיו מאותחלים ל-1 (כל איבר בפני עצמו הוא תת-סדרה עולה באורך 1). 2. עבור $i$ מ-$2$ עד $n$: א. עבור $j$ מ-$1$ עד $i-1$: i. אם $x_j < x_i$ וגם $dp[j] + 1 > dp[i]$: - עדכן: $dp[i] = dp[j] + 1$. 3. התשובה הסופית היא הערך המקסימלי במערך `dp`, כלומר $\max_{1 \le i \le n} dp[i]$. **ניתוח סיבוכיות:** - **זמן ריצה:** האלגוריתם מכיל שתי לולאות מקוננות. הלולאה החיצונית רצה $n-1$ פעמים, והפנימית רצה עד $i-1$ פעמים. בסך הכל, מספר הפעולות הוא פרופורציונלי ל- $\sum_{i=2}^{n} (i-1) = \sum_{k=1}^{n-1} k = \frac{(n-1)n}{2} = \Theta(n^2)$. - **מקום:** אנו משתמשים במערך עזר `dp` בגודל $n$, ולכן סיבוכיות המקום היא $\Theta(n)$. ### פתרון משופר בסיבוכיות $\Theta(n \log n)$ ניתן לייעל את הפתרון הקודם. צוואר הבקבוק בפתרון הריבועי הוא החיפוש אחר $\max \{ dp[j] \mid \dots \}$ בכל איטרציה. במקום זאת, נשנה את הגישה ונשמור מידע אחר. **תובנה מרכזית:** נחזיק מערך `Tails` שבו `Tails[k]` הוא האיבר הקטן ביותר שבו יכולה להסתיים תת-סדרה עולה באורך $k+1$. חשוב להבין שמערך זה **אינו** תת-סדרה עולה בעצמו, אלא כלי עזר. תכונה חשובה של `Tails` היא שהוא תמיד יהיה ממוין בסדר עולה. **אלגוריתם:** 1. אתחל מערך `Tails` ריק. 2. עבור כל איבר $x_i$ בסדרה $s$ (מ-$i=1$ עד $n$): א. אם `Tails` ריק או ש-$x_i$ גדול מהאיבר האחרון ב-`Tails`: - הוסף את $x_i$ לסוף `Tails`. פעולה זו מאריכה את תת-הסדרה העולה הארוכה ביותר שמצאנו עד כה. ב. אחרת (כלומר, $x_i$ אינו גדול מהאיבר האחרון ב-`Tails`): - מצא את האינדקס $j$ של האיבר הראשון ב-`Tails` שגדול או שווה ל-$x_i$. מכיוון ש-`Tails` ממוין, ניתן לעשות זאת באמצעות **חיפוש בינארי**. - החלף את האיבר ב-`Tails` באינדקס $j$ ב-$x_i$. פעולה זו לא משנה את אורך `Tails`, אך היא "משפרת" את הפוטנציאל לעתיד על ידי הקטנת ערך הסיום של תת-סדרה באורך $j+1$. 3. אורך תת-הסדרה העולה המרבי הוא האורך הסופי של המערך `Tails`. **דוגמת הרצה:** $s = (3, 4, -1, 5, 8, 2, 3, 12, 7, 9, 10)$ - $x_1=3$: `Tails` = `[3]` - $x_2=4$: $4 > 3$, הוסף. `Tails` = `[3, 4]` - $x_3=-1$: החלף את 3. `Tails` = `[-1, 4]` - $x_4=5$: $5 > 4$, הוסף. `Tails` = `[-1, 4, 5]` - $x_5=8$: $8 > 5$, הוסף. `Tails` = `[-1, 4, 5, 8]` - $x_6=2$: החלף את 4. `Tails` = `[-1, 2, 5, 8]` - $x_7=3$: החלף את 5. `Tails` = `[-1, 2, 3, 8]` - $x_8=12$: $12 > 8$, הוסף. `Tails` = `[-1, 2, 3, 8, 12]` - $x_9=7$: החלף את 8. `Tails` = `[-1, 2, 3, 7, 12]` - $x_{10}=9$: החלף את 12. `Tails` = `[-1, 2, 3, 7, 9]` - $x_{11}=10$: $10 > 9$, הוסף. `Tails` = `[-1, 2, 3, 7, 9, 10]` האורך הסופי של `Tails` הוא 6, וזהו אורך תת-הסדרה העולה המרבית. (למשל: -1, 2, 3, 7, 9, 10). **ניתוח סיבוכיות:** - **זמן ריצה:** אנו עוברים על כל $n$ האיברים של סדרת הקלט. עבור כל איבר, אנו מבצעים פעולת חיפוש בינארי על המערך `Tails`, שאורכו לכל היותר $n$. חיפוש בינארי לוקח $O(\log k)$ כאשר $k$ הוא אורך `Tails` הנוכחי. לכן, הסיבוכיות הכוללת היא $\Theta(n \log n)$. - **מקום:** אנו משתמשים במערך עזר `Tails` שאורכו לכל היותר $n$, ולכן סיבוכיות המקום היא $\Theta(n)$. $\blacksquare$