שאלת מבחן במבוא למדעי המחשב - הטכניון 2020 - סיבוכיות זמן

שאלה 1 (25 נקודות): א. (8 נקודות) חשבו את סיבוכיות הזמן והמקום של הפונקציה $f1$ המוגדרת בקטע הקוד הבא, כפונקציה של $n$. אין צורך לפרט שיקוליכם. חובה לפשט את הביטוי ככל שניתן. ```c int g(int n) { if(n <= 1) return 1; return g(n / 2) + 1; } void f1(int n) { for(int i = 1; g(i) < n; i *= 2) { printf(" * **\n"); } } ``` סיבוכיות זמן: ____________ סיבוכיות מקום: ____________ ב. (9 נקודות): חשבו את סיבוכיות הזמן והמקום של הפונקציה $f2$ המוגדרת בקטע הקוד הבא, כפונקציה של $n$. אין צורך לפרט שיקוליכם. חובה לפשט את הביטוי ככל שניתן. ```c int g2(int n, int m) { if (m >= n) { for (int i = 0; i < n; ++i) printf("#"); return 1; } return 1 + g2(n / 2, 4 * m); } int f2(int n) { return g2(n, 1); } ``` סיבוכיות זמן: ____________ סיבוכיות מקום: ____________ ג. (8 נקודות): חשבו את סיבוכיות הזמן והמקום של הפונקציה $f3$ המוגדרת בקטע הקוד הבא, כפונקציה של $n$. אין צורך לפרט שיקוליכם. חובה לפשט את הביטוי ככל שניתן. ```c void f1(int n) { int x = 0; for (int i = 0; i <= n / 2; i += 3) for (int j = i; j <= n / 4; j += 2) x++; } ``` סיבוכיות זמן: ____________ סיבוכיות מקום: ____________

רמז: לכל תת-שאלה, יש לקבוע תחילה כמה פעמים הלולאה/רקורסיה מתבצעת כפונקציה של $n$, ולאחר מכן לחשב את עלות כל איטרציה/קריאה בנפרד. שימו לב שתנאי העצירה של הלולאה ב-f1 מגדיר מספר איטרציות שהוא $\Theta(n)$, ולא לוגריתמי.

פתרון: **א. ניתוח f1 ו-g** **פונקציה g:** מחשבת $g(n) = \lfloor \log_2 n \rfloor + 1$, כלומר $g(2^k) = k+1$. **לולאת f1:** $i$ מתחיל ב-1 ומוכפל ב-2 בכל איטרציה. אחרי $k$ איטרציות, $i = 2^k$. תנאי העצירה: $g(i) < n$, כלומר $k+1 < n$, כלומר $k < n-1$. הלולאה רצה עבור $k = 0, 1, \ldots, n-2$, סה"כ $\Theta(n)$ איטרציות. **זמן:** בכל איטרציה $k$, קריאה ל-$g(2^k)$ עולה $\Theta(k)$. סך הזמן: $$\sum_{k=0}^{n-2} \Theta(k) = \Theta\!\left(\frac{n^2}{2}\right) = \Theta(n^2)$$ **מקום:** עומק הרקורסיה של $g(i)$ עבור $i = 2^{n-2}$ הוא $\Theta(n)$. מכיוון שהקריאות ל-$g$ אינן מקביליות, **סיבוכיות מקום: $\Theta(n)$**. --- **ב. ניתוח f2 ו-g2** **g2(n, m):** בכל קריאה רקורסיבית: $n \to n/2$, $m \to 4m$. אחרי $k$ קריאות: $n_k = n/2^k$, $m_k = 4^k$. עצירה כאשר $m_k \ge n_k$: $$4^k \ge \frac{n}{2^k} \implies 8^k \ge n \implies k \ge \log_8 n$$ עומק הרקורסיה: $k^* = \lceil \log_8 n \rceil = \Theta(\log n)$. **ערך $n_{k^*}$ בבסיס הרקורסיה:** $$n_{k^*} = \frac{n}{2^{\log_8 n}} = \frac{n}{n^{\log_8 2}} = n^{1 - \frac{1}{3}} = n^{2/3}$$ הלולאה בבסיס רצה $\Theta(n^{2/3})$ פעמים. **זמן:** כל קריאה לא-בסיסית עולה $O(1)$, ויש $\Theta(\log n)$ כאלו; הבסיס עולה $\Theta(n^{2/3})$: $$T = \Theta(\log n + n^{2/3}) = \Theta(n^{2/3})$$ **מקום:** עומק מחסנית הרקורסיה הוא $\Theta(\log n)$, כל מסגרת $O(1)$: **סיבוכיות זמן: $\Theta(n^{2/3})$, סיבוכיות מקום: $\Theta(\log n)$** --- **ג. ניתוח f3 (לולאות מקוננות)** **לולאה חיצונית:** $i$ מ-0 עד $n/2$, צעד 3 — $\Theta(n)$ איטרציות. **לולאה פנימית:** $j$ מ-$i$ עד $n/4$, צעד 2. כאשר $i > n/4$, הלולאה אינה מתבצעת כלל. לכן תרומה ממשית רק עבור $i \in \{0, 3, 6, \ldots, \lfloor n/4 \rfloor\}$: $$\text{מספר איטרציות פנימיות} \approx \sum_{t=0}^{n/12} \frac{n/4 - 3t}{2} = \frac{1}{2}\left[\frac{n}{12} \cdot \frac{n}{4} - 3 \cdot \frac{(n/12)^2}{2}\right]$$ $$= \frac{1}{2}\left[\frac{n^2}{48} - \frac{n^2}{96}\right] = \frac{n^2}{192} = \Theta(n^2)$$ **מקום:** אין רקורסיה, רק משתנים בודדים $\Rightarrow \Theta(1)$. **סיבוכיות זמן: $\Theta(n^2)$, סיבוכיות מקום: $\Theta(1)$**