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

[4] (25 נקודות) רביעייה פיתגורית היא רביעיה של ארבעה מספרים שלמים חיוביים $(a,b,c,d)$ כך ש $d = \sqrt{a^2 + b^2 + c^2}$. בהינתן מערך $A$ המכיל $n$ מספרים שלמים חיוביים, תארו אלגוריתם הרץ בזמן $O(n^2)$ בממוצע או אלגוריתם אחר הרץ בזמן $O(n^2 \log n)$ במקרה הגרוע המחליט האם קיים ב $A$ רביעייה פיתגורית, כאשר מספרים מ $A$ יכולים להופיע יותר מפעם אחת באותה הרביעייה. הראו אחת משתי האפשרויות.

רמז: שנו את המשוואה $d^2 = a^2 + b^2 + c^2$ לצורה $a^2 + b^2 = d^2 - c^2$. כעת, חשבו כיצד למצוא ביעילות ערך משותף בין קבוצת הסכומים וקבוצת ההפרשים.

פתרון: הבעיה דורשת למצוא האם קיימים ארבעה מספרים $a,b,c,d$ במערך הנתון $A$ (עם אפשרות לחזרות) המקיימים את המשוואה $d^2 = a^2 + b^2 + c^2$. אלגוריתם נאיבי הבודק את כל $n^4$ הרביעיות האפשריות ידרוש זמן של $O(n^4)$, שאינו יעיל מספיק. כדי לשפר את הסיבוכיות, נארגן מחדש את המשוואה כדי שנוכל להשתמש בטכניקת "פגישה באמצע" (meet-in-the-middle). נעביר את $c^2$ אגף ונקבל: $a^2 + b^2 = d^2 - c^2$ כעת, הבעיה הופכת לחיפוש ערך משותף בין קבוצת כל הסכומים מהצורה $a^2 + b^2$ וקבוצת כל ההפרשים מהצורה $d^2 - c^2$, כאשר $a, b, c, d$ הם איברים מהמערך $A$. ניתן לפתור זאת ביעילות באמצעות **טבלת גיבוב** (hash table) כדי להשיג סיבוכיות זמן ממוצעת של $O(n^2)$. להלן תיאור האלגוריתם: 1. **יצירת קבוצת סכומים:** ניצור טבלת גיבוב (או קבוצה מבוססת גיבוב, hash set) בשם `sums_set`. נעבור על כל הזוגות האפשריים של איברים $(a, b)$ מהמערך $A$ (ישנם $n^2$ זוגות כאלה). עבור כל זוג, נחשב את הסכום $S = a^2 + b^2$ ונכניס אותו ל-`sums_set`. שלב זה דורש $O(n^2)$ איטרציות. כל הכנסה לטבלת גיבוב לוקחת בממוצע $O(1)$, ולכן הסיבוכיות הממוצעת של שלב זה היא $O(n^2)$. 2. **חיפוש הפרשים תואמים:** נעבור שוב על כל הזוגות האפשריים של איברים $(c, d)$ מהמערך $A$. עבור כל זוג, נחשב את ההפרש $D = d^2 - c^2$. נבדוק האם הערך $D$ קיים בטבלת הגיבוב `sums_set`. פעולת החיפוש בטבלת גיבוב לוקחת $O(1)$ בממוצע. אם $D$ נמצא ב-`sums_set`, המשמעות היא שמצאנו זוג $(a, b)$ וזוג $(c, d)$ כך ש-$a^2+b^2=d^2-c^2$. במקרה זה, מצאנו רביעייה פיתגורית, והאלגוריתם יכול להחזיר `True` ולסיים. שלב זה כולל $n^2$ איטרציות, ובכל אחת מהן מתבצע חישוב וחיפוש בטבלת גיבוב. לכן, הסיבוכיות הממוצעת של שלב זה היא $O(n^2)$. 3. **סיום ללא מציאה:** אם האלגוריתם מסיים את כל הלולאות בשלב 2 ולא מוצא התאמה, פירוש הדבר שלא קיימת רביעייה פיתגורית במערך $A$. במקרה זה, האלגוריתם יחזיר `False`. **ניתוח סיבוכיות:** - **סיבוכיות זמן:** שני השלבים העיקריים פועלים בזמן $O(n^2)$ בממוצע. לכן, **סיבוכיות הזמן הכוללת של האלגוריתם היא $O(n^2)$ בממוצע**. במקרה הגרוע (התנגשויות רבות בטבלת הגיבוב), הסיבוכיות עלולה להיות גבוהה יותר, אך בממוצע היא עומדת בדרישה. - **סיבוכיות מקום:** טבלת הגיבוב `sums_set` עשויה לאחסן עד $O(n^2)$ ערכים שונים. לכן, **סיבוכיות המקום של האלגוריתם היא $O(n^2)$**. האלגוריתם המוצג פותר את הבעיה בסיבוכיות הזמן הממוצעת הנדרשת. $\blacksquare$