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

ציינו את סיבוכיות הזמן במקרה הגרוע של שלוש הפונקציות הבאות, כתלות ב-n, אורך רשימת הקלט L. תנו תשובה במונחים אסימפטוטיים. התעלמו מגודלם של המספרים המעורבים בחישוב. אין צורך להסביר. ```python def f1(L): n = len(L) for i in range(n): if i in L: L.append(i) return L ``` ```python def f2(L): n = len(L) res = [] for i in range(500, n): for j in range(i, 3*i): k = 1 while k < n: k *= 2 res.append(k) return res ``` ```python def f3(L): n = len(L) if n < 1: return None f3(L[0:(2*n)//3]) return None ``` מהי סיבוכיות הזמן של כל אחת מהפונקציות?

רמז: עבור f1: שימו לב שה-`in` על רשימה הוא O(n), וה-append לא משנה את range כי n נקבע מראש. עבור f2: הלולאה החיצונית O(n), הפנימית O(i) ≈ O(n), ו-while הוא O(log n). עבור f3: פתרו את נוסחת הנסיגה T(n) = T(2n/3) + O(n).

פתרון: **f1:** הלולאה רצה n פעמים. בכל איטרציה, `i in L` לוקח O(n) (חיפוש ברשימה). לכן הסיבוכיות היא **O(n²)**. **f2:** הלולאה החיצונית רצה O(n) פעמים. עבור כל i, הלולאה הפנימית רצה O(i) פעמים. בתוך הלולאה הפנימית, ה-while רץ O(log n) פעמים. סה"כ: $\sum_{i=500}^{n} i \cdot \log n = O(n^2 \log n)$. הסיבוכיות היא **O(n² log n)**. **f3:** נוסחת הנסיגה: T(n) = T(2n/3) + O(n) (כי חיתוך הרשימה L[0:(2*n)//3] לוקח O(n)). לפי משפט המאסטר (או פתיחה): T(n) = O(n) + O(2n/3) + O(4n/9) + ... = O(n · (1 + 2/3 + 4/9 + ...)) = O(n · 3) = **O(n)**.