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

נתונים שני מערכים ממוינים $A$ ו-$B$ של גודל $m$ ו-$n$ בהתאמה. הדחף בגדול $m$ ו-$n$, תמיד מספר משהו $X$ על ספר משהו $X$. בדוגמא לדעת התאם קיימים $a \in A$, $b \in B$ כך ש $a + b = X$. כתוב \ אלגוריתם שבודקת זאת בזמן $O(m+n)$.

רמז: השתמשו בשני מצביעים, אחד שמתחיל בתחילת המערך הראשון והשני שמתחיל בסוף המערך השני. קדמו את המצביעים באופן לינארי על סמך סכום האיברים שהם מצביעים עליהם.

פתרון: הפתרון היעיל לבעיה זו מנצל את העובדה ששני המערכים ממוינים ומשתמש בטכניקת **שני המצביעים** (Two Pointers). האלגוריתם פועל באופן הבא: 1. אתחול שני מצביעים: * מצביע `i` המצביע לתחילת מערך $A$ (אינדקס 0). * מצביע `j` המצביע לסוף מערך $B$ (אינדקס $n-1$). 2. נבצע לולאה כל עוד המצביעים לא חרגו מגבולות המערכים, כלומר כל עוד $i < m$ וגם $j \ge 0$. בכל איטרציה של הלולאה: * נחשב את הסכום הנוכחי: $S = A[i] + B[j]$. * נשווה את $S$ לערך המטרה $X$: * אם $S = X$: מצאנו זוג איברים שסכומם הוא $X$. האלגוריתם יחזיר `true` ויסיים. * אם $S < X$: הסכום הנוכחי קטן מדי. כדי להגדיל את הסכום, עלינו לבחור איבר גדול יותר. מכיוון שמערך $A$ ממוין בסדר עולה, נקדם את המצביע $i$ לאיבר הבא: $i \leftarrow i + 1$. קידום $i$ מגדיל (או לא משנה) את ערך $A[i]$ ובכך את הסכום, ומקרב אותנו לפתרון. * אם $S > X$: הסכום הנוכחי גדול מדי. כדי להקטין את הסכום, עלינו לבחור איבר קטן יותר. מכיוון שמערך $B$ ממוין בסדר עולה, והתחלנו מהסוף, נזיז את המצביע $j$ לאיבר הקודם: $j \leftarrow j - 1$. הזזת $j$ אחורה מקטינה (או לא משנה) את ערך $B[j]$ ובכך את הסכום. 3. אם הלולאה מסתיימת (מצב בו $i \ge m$ או $j < 0$) מבלי שנמצא זוג שסכומו $X$, פירוש הדבר שזוג כזה אינו קיים. במקרה זה, האלגוריתם יחזיר `false`. **הוכחת נכונות:** בכל צעד, האלגוריתם פוסל איבר אחד מהמשך החיפוש: אם $A[i] + B[j] < X$, אנו פוסלים את $A[i]$. אם $A[i] + B[j] > X$, אנו פוסלים את $B[j]$. - כאשר $A[i] + B[j] < X$, אנו פוסלים את $A[i]$. האם זה מוצדק? כן, כי לכל איבר $B[k]$ עם $k \le j$, יתקיים $B[k] \le B[j]$ (כי $B$ ממוין), ולכן $A[i] + B[k] \le A[i] + B[j] < X$. כלומר, $A[i]$ לא יכול ליצור את הסכום $X$ עם אף אחד מהאיברים הנותרים ב-$B$ (אלה שמימין ל-$j$ כבר נפסלו). - כאשר $A[i] + B[j] > X$, אנו פוסלים את $B[j]$. האם זה מוצדק? כן, כי לכל איבר $A[k]$ עם $k \ge i$, יתקיים $A[k] \ge A[i]$ (כי $A$ ממוין), ולכן $A[k] + B[j] \ge A[i] + B[j] > X$. כלומר, $B[j]$ לא יכול ליצור את הסכום $X$ עם אף אחד מהאיברים הנותרים ב-$A$. האלגוריתם סורק את כל הזוגות האפשריים באופן שיטתי, ובכל צעד פוסל באופן נכון חלק ממרחב החיפוש, ולכן הוא נכון. $\blacksquare$ **ניתוח סיבוכיות:** * **סיבוכיות זמן:** בכל איטרציה של הלולאה, או ש-$i$ גדל ב-1 או ש-$j$ קטן ב-1. $i$ מתחיל ב-0 ונעצר ב-$m$, ו-$j$ מתחיל ב-$n-1$ ונעצר ב-1-. לכן, מספר האיטרציות הכולל חסום על ידי $m+n$. כל איטרציה היא $O(1)$, ולכן **סיבוכיות הזמן** הכוללת היא $O(m+n)$. * **סיבוכיות מקום:** האלגוריתם משתמש במספר קבוע של משתנים נוספים (שני מצביעים ומשתנה לסכום), ללא תלות בגודל הקלט. לכן, **סיבוכיות המקום** היא $O(1)$.