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

מבנה $S$ תומך בארבע פעולות על מערך $A[1..n]$. כמו כן, נתון כי המערך $A$ מכיל מספרים טבעיים שונים. להלן 4 הפעולות של המבנה $S$: * $\text{init}(A)$ – חסום בזמן $O(n)$: * איתחול המבנה * $\text{find10}(i,j)$ – חסום בזמן $O(1)$: * מחזיר את האיבר $k$ שהינו העשירי בגודלו בתת המערך $A$ בטווח מ-$i$ עד $j$ ואת האינדקס של $k$ (במקרה ש- $j-i+1 < 10$ הפונקציה תחזיר `null`). * $\text{update}(i,k)$ – חסום בזמן $O(1)$: * מעדכן במערך $A$ את הערך באינדקס $i$ להיות $k$. * $\text{read}(i)$ – חסום בזמן $O(1)$: * מחזיר את האיבר $k$ באינדקס $i$ במערך $A$. תאר מימוש של מבנה נתונים $S$ העומד בדרישות הנ"ל או הוכח שלא קיים מבנה נתונים כזה. דוגמא להבהרה: נתון המערך $A$ הבא: ```text A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[11] A[12] A[13] A[14] A[15] A[16] 4 7 12 2 6 1 8 99 23 76 89 24 42 71 58 90 ``` הפעולה $\text{find10}(2,12)$ תחזיר את הערך: 89 והאינדקס: 11. הפעולה $\text{update}(13,54)$ מערך $A$ לאחר הפעולה יהיה: ```text A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[11] A[12] A[13] A[14] A[15] A[16] 4 7 12 2 6 1 8 99 23 76 89 24 54 71 58 90 ``` הפעולה $\text{read}(6)$ תחזיר את הערך: 1

רמז: נסו להוכיח בדרך השלילה שלא קיים מבנה נתונים כזה. התמקדו בפעולת $\text{find10}(1, n)$ והראו, באמצעות טיעון יריב, שסיבוכיות הזמן שלה במקרה הגרוע חייבת להיות $\Omega(n)$, בסתירה לדרישה.

פתרון: לא קיים מבנה נתונים כזה. נוכיח זאת על ידי הוכחה בדרך השלילה. נניח בשלילה שקיים מבנה נתונים $S$ העומד בדרישות. נתמקד בפעולה $\text{find10}(i,j)$ ובדרישת סיבוכיות הזמן שלה, $O(1)$. דרישה זו צריכה להתקיים עבור כל $i,j$ חוקיים, ובפרט עבור הטווח $[1, n]$, כלומר $\text{find10}(1,n)$ צריכה לרוץ בזמן $O(1)$ (בהנחה ש-$n \ge 10$). כעת, נראה שכל אלגוריתם נכון לבעיית מציאת האיבר העשירי בגודלו במערך $A$ בגודל $n$ חייב לבדוק לפחות $n-9$ איברים מהמערך במקרה הגרוע. מכך נובע שסיבוכיות הזמן של כל אלגוריתם כזה היא $\Omega(n)$. נוכיח טענה זו באמצעות **טיעון יריב (adversary argument)**. נניח שקיים אלגוריתם $\mathcal{A}$ המוצא את האיבר העשירי בגודלו במערך $A$ והוא קורא פחות מ-$n-9$ איברים. כלומר, האלגוריתם קורא $k < n-9$ איברים מהמערך $A$ לפני שהוא מוציא פלט. יהי $R$ אוסף האינדקסים שהאלגוריתם $\mathcal{A}$ קרא, ויהי $U$ אוסף האינדקסים שהאלגוריתם $\mathcal{A}$ **לא** קרא. על פי ההנחה, $|R| = k$ ו-$|U| = n-k > 9$. היריב מנהל את המשחק באופן הבא: עבור כל שאילתה של $\mathcal{A}$ על איבר $A[i]$ כאשר $i \in R$, היריב מספק ערך. לאחר ש-$k$ השאילתות הסתיימו, האלגוריתם $\mathcal{A}$ מוציא פלט $(v, \text{idx})$. כעת, היריב צריך להראות שפלט זה יכול להיות שגוי. היריב עושה זאת על ידי השלמת המערך $A$ (כלומר, קביעת ערכים לאינדקסים ב-$U$) בשתי דרכים שונות, כך שהתשובה הנכונה בכל אחת מהדרכים שונה מהשנייה. מאחר שהאלגוריתם $\mathcal{A}$ כבר סיים את ריצתו ואינו יכול לשנות את תשובתו (כי הוא ראה את אותם הערכים באינדקסים שב-$R$ בשני המקרים), הוא בהכרח יטעה לפחות באחד מהמקרים. נבנה את שתי ההשלמות של היריב: יהיו הערכים שהאלגוריתם קרא $v_1, v_2, \dots, v_k$. תהי $M$ חסם עליון על ערכים אלו ($M = \max(v_1, \dots, v_k)$ אם $k>0$, אחרת $M=0$). * **השלמה 1:** היריב קובע את כל הערכים באינדקסים $j \in U$ להיות מספרים קטנים מאוד (למשל, קטנים יותר מכל הערכים $v_1, \dots, v_k$). במקרה זה, 10 האיברים הגדולים ביותר במערך $A$ נמצאים כולם בקרב האיברים שהאלגוריתם $\mathcal{A}$ קרא. תהי התשובה הנכונה עבור מערך זה $ans_1$. * **השלמה 2:** מכיוון ש-$|U| > 9$, היריב יכול לבחור 10 אינדקסים שונים מתוך $U$, למשל $j_1, \dots, j_{10} \in U$. הוא קובע את הערכים באינדקסים אלה להיות $M+1, M+2, \dots, M+10$. את שאר האינדקסים ב-$U$ (אם ישנם) הוא קובע לערכים קטנים מאוד. במקרה זה, 10 האיברים הגדולים ביותר במערך $A$ הם $M+1, \dots, M+10$. האיבר העשירי בגודלו הוא $M+1$. לכן, התשובה הנכונה עבור מערך זה היא $ans_2 = (M+1, j_1)$. האלגוריתם $\mathcal{A}$ חייב להוציא את אותו הפלט $(v, \text{idx})$ עבור שתי ההשלמות, מכיוון שבמהלך ריצתו הוא "ראה" את אותם הערכים בדיוק (הערכים באינדקסים $R$). עם זאת, התשובות הנכונות $ans_1$ ו-$ans_2$ שונות זו מזו (ערך התשובה ב-$ans_1$ הוא אחד מ-$v_i$ ולכן קטן או שווה ל-$M$, בעוד ערך התשובה ב-$ans_2$ הוא $M+1$). לכן, הפלט של $\mathcal{A}$ אינו יכול להיות נכון עבור שתי ההשלמות. זוהי סתירה להנחה ש-$\mathcal{A}$ הוא אלגוריתם נכון. מכאן, כל אלגוריתם נכון חייב לקרוא לפחות $n-9$ איברים מהמערך. פעולת קריאה של איבר מהמערך לוקחת לפחות זמן קבוע, ולכן סיבוכיות הזמן המינימלית (במקרה הגרוע) למציאת האיבר העשירי בגודלו היא $\Omega(n-9) = \Omega(n)$. דרישת השאלה היא ש-$\text{find10}(i,j)$ תתבצע בסיבוכיות $O(1)$. עבור $i=1, j=n$, יש לנו סתירה: מצד אחד, הפעולה צריכה לרוץ ב-$O(1)$, ומצד שני הראנו שהיא דורשת לפחות $\Omega(n)$ זמן. הסתירה מוכיחה כי ההנחה הראשונית שלנו הייתה שגויה, ולכן לא קיים מבנה נתונים $S$ העומד בכל הדרישות. $\blacksquare$