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

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

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

פתרון: הבעיה דורשת לקבוע האם קיימים במערך הנתון $A$ ארבעה איברים (לאו דווקא שונים) $a, b, c, d$ המקיימים את המשוואה $a^2 + b^2 + c^2 = d^2$. אלגוריתם נאיבי הבודק את כל $n^4$ הרביעיות האפשריות יהיה איטי מדי. כדי למצוא פתרון יעיל יותר, נבצע תחילה סידור מחדש של המשוואה: $a^2 + b^2 = d^2 - c^2$ התובנה המרכזית היא שאם קיימת רביעייה כזו, אז קיים ערך $v$ שניתן להציגו גם כסכום של שני ריבועים ($a^2+b^2$) וגם כהפרש של שני ריבועים ($d^2-c^2$). הדבר מוביל לאלגוריתם המבוסס על שני שלבים: יצירת כל הסכומים האפשריים, ואז בדיקה מול כל ההפרשים האפשריים. נשתמש ב**טבלת גיבוב (hash table)** כדי לבצע את הבדיקה ביעילות. **תיאור האלגוריתם:** 1. **שלב א': חישוב ואחסון סכומי ריבועים** ניצור טבלת גיבוב ריקה, `sums_set`, שתשמש לאחסון כל ערכי $a^2+b^2$ האפשריים. נעבור על כל זוג איברים $(a, b)$ במערך $A$ באמצעות שתי לולאות מקוננות. עבור כל זוג, נחשב את הערך $s = a^2 + b^2$ ונכניס אותו ל-`sums_set`. שלב זה כולל $n^2$ איטרציות. כל פעולת הכנסה לטבלת גיבוב היא בממוצע $O(1)$, ולכן סיבוכיות הזמן של שלב זה היא $O(n^2)$ בממוצע. 2. **שלב ב': חיפוש הפרשי ריבועים** כעת, נעבור על כל זוג איברים $(c, d)$ במערך $A$, שוב באמצעות שתי לולאות מקוננות. עבור כל זוג, נחשב את הערך $v = d^2 - c^2$. נבדוק האם הערך $v$ קיים בטבלת הגיבוב `sums_set`. פעולת החיפוש בטבלת גיבוב היא בממוצע $O(1)$. אם $v$ נמצא ב-`sums_set`, פירוש הדבר שמצאנו איברים $a, b, c, d$ כך ש-$a^2 + b^2 = d^2 - c^2$. זוהי למעשה המשוואה המקורית $a^2 + b^2 + c^2 = d^2$. במקרה כזה, האלגוריתם מצא פתרון ויכול להחזיר `true`. 3. **סיום:** אם האלגוריתם מסיים את כל הלולאות בשלב ב' מבלי למצוא התאמה, פירוש הדבר שאין רביעייה כזו במערך, והאלגוריתם יחזיר `false`. **ניתוח סיבוכיות:** * **סיבוכיות זמן:** האלגוריתם מורכב משני שלבים, כל אחד מהם דורש $O(n^2)$ פעולות בממוצע (לולאות מקוננות עם פעולות גיבוב). לכן, **סיבוכיות הזמן** הכוללת היא $O(n^2)$. * **סיבוכיות מקום:** אנו מאחסנים עד $O(n^2)$ סכומים שונים בטבלת הגיבוב. לכן, **סיבוכיות המקום** היא $O(n^2)$. האלגוריתם עונה על דרישת השאלה לפתרון בסיבוכיות זמן $O(n^2)$. $\blacksquare$