הבהרה בנוגע לשימוש בלשון זכר: כדי למנוע סרבול מיותר, וכמקובל בשפה העברית, ננקטת לעתים לשון זכר בהתייחסות אל כלל הגולשות והגולשים ובמתן שמות לערכים. אנא קבלו זאת בהבנה.
שימו לב:
*נא להגיש רק את שאלות 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}
שורות. כל כניסה במטריצה היא 0 או 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}
מספר
שלם גדול ממש מ1,
b
{\displaystyle \displaystyle b}
מספר גדול ממש מ1, ו
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}
שלם גדול ממש מ1.
אנא הוכח
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)}
.