שאלת מבחן במבוא למדעי המחשב - אוניברסיטת בר-אילן 2024 - מעקב אחר קוד

התכנית הבאה מתקמפלת ורצה. ```c void f(int x[], int i, int j) { int a, b; if (x[i] > x[j]){ a = x[i]; x[i] = x[j]; x[j] = a; } if ((i + 3) >= j) return; b = (j - i+1) / 4; f(x, i, j - b); f(x, i + b, j); } int main(){ int b[] = {1, 33, 22, 4, 2, 66}; int n = sizeof(b)/sizeof(b[0]); int c=0; f(b, 0, n-1); for (;c < n;c++) printf("%d ", b[c]); return 0; } ``` (4 נק') מה פלט התכנית? (4 נק') מה סיבוכיות התכנית ב-$\Theta$? (הציגו את הנוסחה, הראו את דרך הפתרון ואת התוצאה הסופית)

רמז: הפונקציה מבצעת swap בין x[i] ו-x[j] אם הם לא בסדר, ואז קוראת רקורסיבית על 3/4 הראשונים ו-3/4 האחרונים של הטווח. תנאי העצירה: כשהטווח קטן מ-4 אלמנטים.

פתרון: **פלט:** **f(b, 0, 5):** b = {1, 33, 22, 4, 2, 66} - b[0]=1 < b[5]=66, no swap. - (0+3)≥5? No. b = (5-0+1)/4 = 1. - f(b, 0, 4) → f(b, 1, 5) **f(b, 0, 4):** b[0]=1 < b[4]=2, no swap. (0+3)≥4? No. b=1. - f(b, 0, 3): 1 < 4, no swap. (0+3)≥3? **Yes, return.** - f(b, 1, 4): b[1]=33 > b[4]=2 → **swap** → b = {1, **2**, 22, 4, **33**, 66}. (1+3)≥4? **Yes, return.** **f(b, 1, 5):** b[1]=2 < b[5]=66, no swap. (1+3)≥5? No. b=1. - f(b, 1, 4): 2 < 33, no swap. (1+3)≥4? **Yes, return.** - f(b, 2, 5): 22 < 66, no swap. (2+3)≥5? **Yes, return.** **תוצאה:** `1 2 22 4 33 66` **סיבוכיות:** $n = j - i + 1$. שתי קריאות רקורסיביות, כל אחת על גודל $3n/4$. עבודה $O(1)$ בכל קריאה. $$T(n) = 2T(3n/4) + O(1)$$ **Master Theorem:** $a = 2$, $b = 4/3$. $$\log_{4/3} 2 = \frac{\ln 2}{\ln(4/3)} = \frac{0.693}{0.288} \approx 2.41$$ $f(n) = O(1) = O(n^{2.41 - \epsilon})$ → **מקרה 1:** $$\boxed{T(n) = \Theta(n^{\log_{4/3} 2}) \approx \Theta(n^{2.41})}$$ $\blacksquare$