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

[1] ראינו כיצד להכפיל שני מספרים $X, Y$, כל אחד בעל $n$ סיביות בשיטת הפרד ומשול בזמן $O(n^2)$, כאשר כל מספר חולק לשני חלקים באורך $n/2$ סיביות כל אחד. כאשר צמצמנו את מספר הקריאות הרקורסיביות מ 4 ל 3, הסיבוכיות ירדה ל $O(n^{1.58})$. שאלה זאת דנה בהצעה לחלק כל מספר ל3 חלקים באורך שווה, במקום רק ל2. סעיף 5 נקודות. א) הגדירו את $X$ ו $Y$ כל אחד כפונקציה של שלושת חלקיהם $X_1,X_2,X_3$ ו $Y_1,Y_2,Y_3$ ב) הראו איך ניתן לחשב את $X*Y$ ע"י 9 קריאות רקורסיביות (הפרד) ועוד עבודת איסוף התוצאות שעלותה לינארית ב $n$ (ומשול) ג) מה הסיבוכיות של שיטה זו? ד) בדומה למה שראינו במקרה של חלוקה ל2 חלקים, הראו איך, ע"י חישוב שלושת הערכים הבאים: $G = (X_1 + X_3)(Y_1 + Y_3)$ , $F = (X_2 + X_3)(Y_2 + Y_3)$ , $E = (X_1 + X_2)(Y_1 + Y_2)$ ניתן להוריד את מספר הקריאות הרקורסיביות מ9 ל 6. ה) מה הנוסחה המתקבלת עבור הסיבוכיות? (3 נקודות) בונוס: האם כדאי לחלק ל3?

רמז: כתבו את נוסחת הנסיגה עבור כל שיטה והשוו את הסיבוכיות המתקבלת באמצעות משפט המאסטר לסיבוכיות של אלגוריתם קרצובה.

פתרון: א) **הגדרת X ו-Y לפי שלושת חלקיהם** נניח כי מספר הסיביות $n$ הוא חזקה של 3. נחלק כל מספר $X$ ו-$Y$ לשלושה חלקים באורך $m = n/3$ סיביות כל אחד. נסמן את החלקים $X_1, X_2, X_3$ (מהבכיר לזוטר) ואת $Y_1, Y_2, Y_3$ (מהבכיר לזוטר). אזי ניתן לייצג את המספרים באופן הבא: $X = X_1 eta^{2} + X_2 eta + X_3$ $Y = Y_1 eta^{2} + Y_2 eta + Y_3$ כאשר $\beta = 2^m = 2^{n/3}$. ב) **חישוב $X imes Y$ באמצעות 9 קריאות רקורסיביות** נכפיל את הביטויים שקיבלנו בסעיף א': $X imes Y = (X_1 \beta^2 + X_2 \beta + X_3) imes (Y_1 \beta^2 + Y_2 \beta + Y_3)$ פתיחת הסוגריים וסידור לפי חזקות של $\beta$ נותנת: $X imes Y = (X_1 Y_1) \beta^4 + (X_1 Y_2 + X_2 Y_1) \beta^3 + (X_1 Y_3 + X_2 Y_2 + X_3 Y_1) \beta^2 + (X_2 Y_3 + X_3 Y_2) \beta + (X_3 Y_3)$ כדי לחשב את התוצאה, עלינו לחשב את כל 9 המכפלות האפשריות של חלקי המספרים: $X_i Y_j$ עבור $i, j \in \{1, 2, 3\}$. כל מכפלה כזו היא **קריאה רקורסיבית** לכפל של מספרים באורך $n/3$. שלב ה**"ומשול"** כולל חיבור והזזה (כפל בחזקות של $\beta$) של התוצאות. פעולות אלה הן לינאריות בגודל המספרים, כלומר $O(n)$. ג) **ניתוח סיבוכיות** האלגוריתם מבצע 9 קריאות רקורסיביות על קלט בגודל $n/3$, ועבודה נוספת בסיבוכיות לינארית $O(n)$. לכן, **נוסחת הנסיגה** לזמן הריצה $T(n)$ היא: $T(n) = 9 T(n/3) + O(n)$ נשתמש ב**משפט המאסטר** כדי לפתור את הנוסחה. במקרה זה, $a=9$, $b=3$, ו-$f(n) = O(n)$. נשווה את $f(n)$ ל-$n^{\log_b a} = n^{\log_3 9} = n^2$. מכיוון ש-$f(n) = O(n) = O(n^{2-\epsilon})$ עבור $\epsilon=1$, אנו במקרה הראשון של משפט המאסטר. לכן, הסיבוכיות היא: $T(n) = \Theta(n^{\log_b a}) = \Theta(n^2)$. זוהי סיבוכיות זהה לשיטת הכפל הבית-ספרית. $\blacksquare$ ד) **הורדת מספר הקריאות הרקורסיביות ל-6** במקום לחשב את כל 9 המכפלות ישירות, נחשב 6 מכפלות באופן הבא: 1. $P_1 = X_1 Y_1$ 2. $P_2 = X_2 Y_2$ 3. $P_3 = X_3 Y_3$ 4. $E = (X_1 + X_2)(Y_1 + Y_2)$ 5. $F = (X_2 + X_3)(Y_2 + Y_3)$ 6. $G = (X_1 + X_3)(Y_1 + Y_3)$ אלו הן 6 קריאות רקורסיביות (החיבורים לפני הכפל לוקחים זמן לינארי). כעת נבטא את המקדמים של $X \times Y$ באמצעות 6 תוצאות אלו: - המקדם של $\beta^4$ הוא $X_1 Y_1 = P_1$. - המקדם של $\beta^0$ הוא $X_3 Y_3 = P_3$. - נשים לב ש: $E = X_1 Y_1 + X_1 Y_2 + X_2 Y_1 + X_2 Y_2 = P_1 + (X_1 Y_2 + X_2 Y_1) + P_2$. לכן, המקדם של $\beta^3$ הוא $X_1 Y_2 + X_2 Y_1 = E - P_1 - P_2$. - באופן דומה: $F = X_2 Y_2 + X_2 Y_3 + X_3 Y_2 + X_3 Y_3 = P_2 + (X_2 Y_3 + X_3 Y_2) + P_3$. לכן, המקדם של $\beta^1$ הוא $X_2 Y_3 + X_3 Y_2 = F - P_2 - P_3$. - לבסוף: $G = X_1 Y_1 + X_1 Y_3 + X_3 Y_1 + X_3 Y_3 = P_1 + (X_1 Y_3 + X_3 Y_1) + P_3$. לכן, המקדם של $\beta^2$ שהוא $X_1 Y_3 + X_2 Y_2 + X_3 Y_1$ שווה ל- $(X_1 Y_3 + X_3 Y_1) + X_2 Y_2 = (G - P_1 - P_3) + P_2$. כל המקדמים הדרושים חושבו באמצעות 6 מכפלות בלבד ופעולות חיבור/חיסור לינאריות. $\blacksquare$ ה) **סיבוכיות השיטה המשופרת** כעת האלגוריתם מבצע 6 קריאות רקורסיביות על קלט בגודל $n/3$, ועבודה נוספת בסיבוכיות $O(n)$. נוסחת הנסיגה היא: $T(n) = 6 T(n/3) + O(n)$ שוב נשתמש במשפט המאסטר: $a=6$, $b=3$, $f(n)=O(n)$. החזקה הקריטית היא $\log_b a = \log_3 6$. מכיוון ש-$f(n) = O(n) = O(n^{\log_3 6 - \epsilon})$ (כי $\log_3 6 \approx 1.63 > 1$), אנו שוב במקרה הראשון של המשפט. הסיבוכיות היא: $T(n) = \Theta(n^{\log_3 6})$. **בונוס: האם כדאי לחלק ל-3?** כדי להכריע, נשווה את סיבוכיות השיטה המוצעת לסיבוכיות אלגוריתם **קרצובה**, שבו מחלקים את המספר ל-2 חלקים ומבצעים 3 קריאות רקורסיביות. הסיבוכיות של קרצובה היא $O(n^{\log_2 3})$. נשווה את המעריכים: - המעריך של קרצובה: $\log_2 3 \approx 1.585$. - המעריך בשיטה המוצעת: $\log_3 6 = \log_3(2 \times 3) = \log_3 2 + \log_3 3 = \log_3 2 + 1 \approx 0.631 + 1 = 1.631$. מכיוון ש-$1.631 > 1.585$, השיטה המוצעת עם 6 הכפלות היא **פחות יעילה** אסימפטוטית מאלגוריתם קרצובה. לכן, לא כדאי להשתמש בה. (הערה: קיימת גרסה אופטימלית יותר של חלוקה ל-3, אלגוריתם Toom-3, המשתמש ב-5 קריאות רקורסיביות ומשיג סיבוכיות של $O(n^{\log_3 5}) \approx O(n^{1.465})$, שהיא טובה יותר מקרצובה).