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

כלל אחרי מהשלושים הבאים בעץ/לא בעץ (20 נקודות): (א) כלל מעץ קיימין מפורטות השמעות $O(n^2)$ בגודל בעץ $n$. ודודל מתבנייות השמעות $O(\log n)$. (ב) בדודר שפירות תכונות-תחזיקה-עד על אחר סדר עיץ-עד על אחר שפירות רדודד $O(\log n)$ זמן עיון. (ג) כלל שמעץ הוא suffix-trie השלם טיקנומיום תכונות מחדודך על גודל $O(n)$. (ד) קיומי זה הואווט-לטוק בחדוק סימן post-orderi שיחתה היא סדרה מונחת כלשהי לרגדודל גדוד. (ה) בנודר שהוא זאת האום הדלוקד x הווכו לבלום-ספרה קטגורה שיחתה שלום "כן" על לקודודו לרגדודל גדוד, אך שהוא מנולם לא דולום לא הוקום לרגדודל גדוד. (ו) בנודר שהוא זאת האום הדלוקד x הווכו לבלום-ספרה קטגורה שיחתה שלום "כן" על לקודודו לרגדודל גדוד על אה שהוקום לרגדודל בעובדה. (ז) כלל מעץ קיימין מפורטות לדודל גודל $\Omega(n)$ בדודד צודודו השמעויות משדודדוק הוא אירוד סדר אחד $O(\log n)$ זמן עיון. (ח) בנודר: שלום מסומן עמודו $\mu = 2^{2^n}$ בדודר בשדודדוך בנתוודר צודודה זמן הקליטות שיודוך/רדודד לרגדודל דודרויותם $y$-fast-trie בנודוד בדודר מנולם שדודוך $AVL$.

רמז: נתחו את סיבוכיות הזמן של פעולה ב-y-fast-trie כתלות בגודל היקום $\mu$, והשוו אותה לסיבוכיות הפעולה בעץ AVL התלויה במספר האיברים $n$. זכרו את כלל הלוגריתם $\log_b(a^c) = c \cdot \log_b(a)$.

פתרון: הטענה המופיעה בסעיף (ח) אינה נכונה. הטענה משווה את ביצועי הזמן של מבני הנתונים **y-fast-trie** ו-**עץ AVL** עבור $n$ איברים מתוך יקום בגודל $\mu = 2^{2^n}$. ננתח את סיבוכיות הזמן של פעולות (כגון הכנסה, מחיקה, חיפוש עוקב) בכל אחד ממבני הנתונים. 1. **עץ AVL**: עבור עץ AVL המכיל $n$ איברים, סיבוכיות הזמן של הפעולות העיקריות היא $O(\log n)$. סיבוכיות זו תלויה רק ב**מספר האיברים** $n$ שבעץ, ולא בגודל היקום שממנו הם נלקחו. 2. **y-fast-trie**: עבור y-fast-trie, סיבוכיות הזמן של הפעולות תלויה ב**גודל היקום**, $\mu$. הסיבוכיות היא $O(\log \log \mu)$. במקרה הנתון, גודל היקום הוא $\mu = 2^{2^n}$. נציב ערך זה בנוסחת הסיבוכיות: $T_{y-fast-trie} = O(\log \log \mu) = O(\log \log (2^{2^n}))$ נפשט את הביטוי בעזרת חוקי לוגריתמים: $\log (2^{2^n}) = 2^n \cdot \log 2 = 2^n$ לכן, $\log(\log(2^{2^n})) = \log(2^n) = n \cdot \log 2 = n$ מכאן שסיבוכיות הזמן עבור y-fast-trie במקרה זה היא $O(n)$. **השוואה:** - זמן ריצה ב-y-fast-trie: $O(n)$ - זמן ריצה בעץ AVL: $O(\log n)$ כאשר משווים את סדרי הגודל, $O(\log n)$ מהיר יותר אסימפטוטית מ-$O(n)$. לכן, עבור יקום בגודל הנתון, עץ AVL יהיה יעיל יותר מ-y-fast-trie. הטענה כי y-fast-trie מהיר יותר מ-AVL היא שגויה. $\blacksquare$