הבהרה בנוגע לשימוש בלשון זכר: כדי למנוע סרבול מיותר, וכמקובל בשפה העברית, ננקטת לעתים לשון זכר בהתייחסות אל כלל הגולשות והגולשים ובמתן שמות לערכים. אנא קבלו זאת בהבנה.
שימו לב:
*נא להגיש רק את שאלות 1-5.
שאר השאלות הן לצורך חזרה למבחן בלבד. אין צורך להגיש את התשובות להן.
הפונקציה
T
(
n
)
{\displaystyle \displaystyle T(n)}
T
(
n
)
=
∑
i
=
1
n
∑
j
=
i
n
[
Θ
(
j
−
i
+
1
)
]
{\displaystyle \displaystyle T(n)=\sum _{i=1}^{n}\sum _{j=i}^{n}[\Theta (j-i+1)]}
אנא הוכח
T
(
n
)
=
Θ
(
n
3
)
{\displaystyle \displaystyle T(n)=\Theta (n^{3})}
רמז
נסה להוכיח זאת באותו אופן בו הוכחנו
∑
i
=
1
n
[
log
(
i
)
]
=
Θ
(
n
⋅
log
(
n
)
)
{\displaystyle \displaystyle \sum _{i=1}^{n}[\log(i)]=\Theta (n\cdot \log(n))}
הוכח בנפרד חסמי
O
{\displaystyle \displaystyle O}
Ω
{\displaystyle \displaystyle \Omega }
ערוך מניפולציות על איבר הטור הכללי ועל גבולות הסיכום כך שיתקבל איבר טור שאינו תלוי בגבולות הסיכום (ולכן ניתן יהיה להוציאו מחוץ לסכום).
אנא מצא חסמים עליונים ותחתונים (כלומר, מסוג
Ω
{\displaystyle \displaystyle \Omega }
O
{\displaystyle \displaystyle O}
T
(
n
)
{\displaystyle \displaystyle T(n)}
T
(
n
)
{\displaystyle \displaystyle T(n)}
T
(
n
)
=
3
⋅
T
(
n
/
2
)
+
n
⋅
log
(
n
)
{\displaystyle \displaystyle T(n)=3\cdot T(n/2)+n\cdot \log(n)}
T
(
n
)
=
T
(
n
−
1
)
+
log
(
n
)
{\displaystyle \displaystyle T(n)=T(n-1)+\log(n)}
T
(
n
)
=
T
(
α
⋅
n
)
+
T
(
(
1
−
α
)
⋅
n
)
+
Θ
(
n
)
{\displaystyle \displaystyle T(n)=T(\alpha \cdot n)+T((1-\alpha )\cdot n)+\Theta (n)}
0
<
α
<
1
{\displaystyle \displaystyle 0<\alpha <1}
בנוסחת הנסיגה
T
(
n
)
=
T
(
n
)
+
log
(
n
)
{\displaystyle \displaystyle T(n)=T({\sqrt {n}})+\log(n)}
T
(
n
)
{\displaystyle \displaystyle T(n)}
T
(
n
)
{\displaystyle \displaystyle T(n)}
T
(
n
)
=
∑
i
=
1
n
−
1
[
T
(
i
)
]
+
Θ
(
n
)
{\displaystyle \displaystyle T(n)=\sum _{i=1}^{n-1}[T(i)]+\Theta (n)}
T
(
n
)
=
Ω
(
1.5
n
)
{\displaystyle \displaystyle T(n)=\Omega (1.5^{n})}
להלן פסוודו-קוד לפונקציה Foo, המקבלת מספר שלם לא-שלילי ומחזירה מספר שלם:
Foo ( n )
1 if n == 0
2 return 0
3 return n % 2 + Foo ( ⌊ n / 2 ⌋ )
אנא הסבר מה עושה הפונקציה (בלווי נימוק), ונתח את סיבוכיותה.
A[1, ..., n] הוא מערך של מספרים שונים זה מזה. נאמר ש
(
i
,
j
)
{\displaystyle \displaystyle (i,j)}
היפוך אם
i
<
j
{\displaystyle \displaystyle i<j}
A[i] > A[j].
במערך [2, 3, 8, 6, 1] יש 5 היפוכים. אנא רשום אותם.
אנא מצא אלגוריתם יעיל למציאת מספר ההיפוכים במערך.
דוגמה:
נניח שיזינו לאלגוריתם שתכתוב את המערך בדוגמה של הסעיף הראשון. הפלט שהאלגוריתם שלך אמור להוציא הוא המספר 5.
רמז
תוכל אולי לשנות את מיון מיזוג . הוסף משתנים גלובליים ופונקציות עזר כרצונך, אם הדבר יעזור לך.
הפונקציה Alg מוגדרת כך:
Alg ( A , i , j )
1 if j <= i + 1
2 return
3 q = Sqrt ( j - i + 1 ) # q = ⌊(j - i + 1)^(1/2)⌋
4 for k in [ 0 , ... , q - 1 ]
5 Alg ( A , i + k * q , i + ( k + 1 ) * ( q - 1 ))
6 Proc ( A , i , j )
היא משתמשת בשתי הפונקציות הבאות:
הפונקציה Sqrt(n) מחזירה את השורש הריבועי של
n
{\displaystyle \displaystyle n}
O
(
1
)
{\displaystyle \displaystyle O(1)}
הפונקציה Proc היא פונקציה כלשהי המקיימת שזמן ריצת Proc(A, i, j) הוא
Θ
(
j
−
i
)
{\displaystyle \displaystyle \Theta (j-i)}
מהו זמן הריצה של Alg(A, 1, n)?
נתונה מטריצה בת
n
{\displaystyle \displaystyle n}
m
=
2
n
−
1
{\displaystyle \displaystyle m=2^{n}-1}
n
{\displaystyle \displaystyle n}
2
n
{\displaystyle \displaystyle 2^{n}}
n
{\displaystyle \displaystyle n}
דוגמה:
עבור
n
=
2
{\displaystyle \displaystyle n=2}
[0, 1] (המתאר בבינרית את המספר 1), השורה השנייה היא המערך [1, 1] (המתאר בבינרית את המספר 3), והשורה השלישית היא המערך [0, 0] (המתאר בבינרית את המספר 0). השורה החסרה היא המערך [1, 0] (המתאר בבינרית את המספר 2).
Θ
(
m
)
{\displaystyle \displaystyle \Theta (m)}
רמז
נסה להפוך את הבעיה לבעיה קטנה בחצי (בערך) בזמן לינארי.
אנא הוכחה את המשפט הבא:
משפט:
פתרון
T
(
n
)
=
max
1
≤
i
≤
n
/
2
[
T
(
i
)
+
T
(
n
−
i
)
+
Θ
(
i
)
]
{\displaystyle \displaystyle T(n)=\max _{1\leq i\leq n/2}[T(i)+T(n-i)+\Theta (i)]}
O
(
n
⋅
log
(
n
)
)
{\displaystyle \displaystyle O\left(n\cdot \log(n)\right)}
T
(
n
)
{\displaystyle \displaystyle T(n)}
T
(
n
)
=
a
⋅
T
(
n
b
)
+
f
(
n
)
{\displaystyle \displaystyle T(n)=a\cdot T\left({\frac {n}{b}}\right)+f(n)}
a
{\displaystyle \displaystyle a}
b
{\displaystyle \displaystyle b}
f
(
n
)
{\displaystyle \displaystyle f(n)}
f
(
n
)
=
Θ
(
n
log
b
(
a
)
log
k
(
n
)
)
{\displaystyle \displaystyle f(n)=\Theta \left(n^{\log _{b}(a)}\log ^{k}(n)\right)}
k
{\displaystyle \displaystyle k}
T
(
n
)
=
Θ
(
n
log
b
(
a
)
log
k
+
1
(
n
)
)
{\displaystyle \displaystyle T(n)=\Theta \left(n^{\log _{b}(a)}\log ^{k+1}(n)\right)}
![{\displaystyle \displaystyle T(n)=\sum _{i=1}^{n}\sum _{j=i}^{n}[\Theta (j-i+1)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e0ad48d0a33c3eee7f7d75e88bd699636abf44e1)
![{\displaystyle \displaystyle \sum _{i=1}^{n}[\log(i)]=\Theta (n\cdot \log(n))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0f116613809a87640ad4c06e60144f9545fa8ad6)
![{\displaystyle \displaystyle T(n)=\sum _{i=1}^{n-1}[T(i)]+\Theta (n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9236d8f52a4bdf6eef62d47a9cc894f85aeaf995)
![{\displaystyle \displaystyle T(n)=\max _{1\leq i\leq n/2}[T(i)+T(n-i)+\Theta (i)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ef62acc75f5d5fb22b3af4c4aa5b098c7db57bda)
