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

נתון משדר $[l...r]$ לא ממוןין על מספרים טבעיים. בצורתונו לזידרה על בסיס העמוקות ש חישוב בינו לזירויות מדוקדק שהאינדקס $A$ מיוצור לזירות מדוקדק. שהרח"אח מעקב אינדקסים שהם אינדקס $A$ מדוקדק לדעות זרך $\Omega(n \log n)$.

רמז: הראו כיצד ניתן לפתור את בעיית בדיקת ייחודיות האיברים (Element Uniqueness), שלה חסם תחתון ידוע, באמצעות אלגוריתם המוצא את זוג האיברים עם ההפרש המינימלי.

פתרון: נוכיח את החסם התחתון הנדרש באמצעות **רדוקציה** מבעיית **בדיקת ייחודיות האיברים** (Element Uniqueness). 1. **הגדרת הבעיות:** * **בעיית הזוג עם ההפרש המינימלי:** בהינתן מערך $A$ של $n$ מספרים, יש למצוא זוג אינדקסים $i eq j$ כך שההפרש $|A[i] - A[j]|$ הוא מינימלי אך גדול מאפס. אם כל האיברים זהים, אין פתרון. * **בעיית בדיקת ייחודיות (Element Uniqueness):** בהינתן מערך $A$ של $n$ מספרים, יש לקבוע האם כל האיברים ב-$A$ שונים זה מזה. 2. **החסם התחתון של בעיית בדיקת הייחודיות:** ידוע כי לבעיית בדיקת הייחודיות יש **חסם תחתון** של $\Omega(n \log n)$ במודל עץ ההחלטה (אלגוריתמים מבוססי-השוואות). כלומר, כל אלגוריתם מבוסס-השוואות הפותר בעיה זו דורש לפחות $\Omega(n \log n)$ השוואות במקרה הגרוע. 3. **הרדוקציה:** נניח בשלילה שקיים אלגוריתם, נקרא לו $FindMinDiff$, הפותר את בעיית הזוג עם ההפרש המינימלי בסיבוכיות זמן $T(n) = o(n \log n)$. נראה כיצד ניתן להשתמש באלגוריתם $FindMinDiff$ כדי לפתור את בעיית בדיקת הייחודיות בזמן $o(n \log n)$, מה שיוביל לסתירה לחסם התחתון הידוע. 4. **בניית אלגוריתם לבדיקת ייחודיות:** נבנה אלגוריתם, נקרא לו $CheckUniqueness$, המשתמש ב-$FindMinDiff$ כתת-שגרה: * **קלט:** מערך $A$ בגודל $n$. * **שלב 1:** קודם כל, נבדוק אם קיימים איברים זהים. ניתן לעשות זאת על ידי מיון המערך והשוואת איברים סמוכים, דבר הדורש $O(n \log n)$. אך אנו רוצים להשתמש ברדוקציה. נניח ש-$FindMinDiff$ יודע להתמודד עם איברים זהים ולהחזיר הפרש 0. הרץ את האלגוריתם $FindMinDiff$ על הקלט $A$. נסמן את ההפרש המינימלי שהוחזר ב-$d$. * **שלב 2:** אם האלגוריתם $FindMinDiff$ מצא זוג איברים זהים, ההפרש המינימלי יהיה $d=0$. אם כל האיברים שונים, ההפרש המינימלי יהיה $d>0$. לכן: * אם $d=0$, זה אומר שקיים זוג $i,j$ כך ש-$A[i]=A[j]$. במקרה זה, לא כל האיברים ייחודיים. החזר "לא ייחודי". * אם $d>0$, זה אומר שלכל זוג $i,j$ מתקיים $A[i] \neq A[j]$. במקרה זה, כל האיברים ייחודיים. החזר "ייחודי". 5. **ניתוח סיבוכיות וסתירה:** האלגוריתם $CheckUniqueness$ שבנינו מורכב מהרצת $FindMinDiff$ (בזמן $T(n)$ לפי ההנחה) וביצוע בדיקה אחת (בזמן $O(1)$). הסיבוכיות הכוללת של $CheckUniqueness$ היא $T(n) + O(1)$. מהנחת השלילה, $T(n) = o(n \log n)$, ולכן גם הסיבוכיות של $CheckUniqueness$ היא $o(n \log n)$. בנינו אלגוריתם הפותר את בעיית בדיקת הייחודיות בסיבוכיות $o(n \log n)$, מה שמהווה **סתירה** לחסם התחתון הידוע של הבעיה שהוא $\Omega(n \log n)$. מכאן שההנחה הראשונית שלנו שגויה. לא ייתכן שקיים אלגוריתם הפותר את בעיית מציאת ההפרש המינימלי בסיבוכיות טובה יותר מ-$\Omega(n \log n)$. לפיכך, כל אלגוריתם מבוסס-השוואות לבעיה זו דורש לפחות $\Omega(n \log n)$ השוואות. $\blacksquare$