שימו לב:
*נא להגיש רק את שאלות 1-5.
שאלה 6 שייכת למעשה לקורס חדו"א. אנא וודאו שהנכם מבינים את המשפט, אך אין צורך להגיש את התשובה.
שאר השאלות הן לצורך חזרה למבחן בלבד. אין צורך להגיש את התשובות להן.
אנא הוכח או הפרך את הטענות הבאות:
80
=
O
(
3
⋅
n
)
{\displaystyle \displaystyle 80=O(3\cdot n)}
.
2
n
+
1003
+
30
=
O
(
2
n
)
{\displaystyle \displaystyle 2^{n+1003}+30=O(2^{n})}
.
2
⋅
n
+
7
=
O
(
2
⋅
n
+
3
)
{\displaystyle \displaystyle 2\cdot n+7=O(2\cdot n+3)}
.
3
⋅
n
=
O
(
1
)
{\displaystyle \displaystyle 3\cdot n=O(1)}
.
log
2
(
n
)
=
O
(
log
10
(
n
)
)
{\displaystyle \displaystyle \log _{2}(n)=O(\log _{10}(n))}
.
שימו לב:
הכוונה בסעיף הראשון לפונקציה הקבועה
f
(
n
)
=
80
{\displaystyle \displaystyle f(n)=80}
, ולא לקבוע 80.
נתונות שתי פונקציות:
f
(
n
)
=
n
+
c
1
n
log
2
(
n
)
{\displaystyle \displaystyle f(n)=n+c_{1}n\log ^{2}(n)}
g
(
n
)
=
n
+
c
2
n
2
{\displaystyle \displaystyle g(n)=n+c_{2}n^{2}}
כאשר
c
1
>
c
2
>
0
{\displaystyle \displaystyle c_{1}>c_{2}>0}
.
האם
f
(
n
)
=
O
(
g
(
n
)
)
{\displaystyle \displaystyle f(n)=O(g(n))}
?
האם
g
(
n
)
=
O
(
f
(
n
)
)
{\displaystyle \displaystyle g(n)=O(f(n))}
?
נתבונן בפסוודו-קוד הבא:
Foo ( n )
1 Bar - 1 ( n )
2 Bar - 2 ( n )
3 Bar - 3 ( n )
נתון:
זמן הריצה של Bar-1(n)
הוא
Ω
(
n
2
log
(
n
)
)
{\displaystyle \displaystyle \Omega (n^{2}\log(n))}
.
זמן הריצה של Bar-2(n)
הוא
Θ
(
n
2
)
{\displaystyle \displaystyle \Theta (n^{2})}
.
זמן הריצה של Bar-3(n)
הוא
O
(
n
)
{\displaystyle \displaystyle O(n)}
.
עבור כל אחד מהחסמים הבאים, אנא ציין האם הוא בהכרח מתקיים, בהכרח לא מתקיים, או שאי אפשר לקבוע בוודאות האם הוא בהכרח מתקיים או לא:
זמן הריצה של Foo(n)
הוא
Ω
(
n
)
{\displaystyle \displaystyle \Omega (n)}
.
זמן הריצה של Foo(n)
הוא
Ω
(
n
3
)
{\displaystyle \displaystyle \Omega (n^{3})}
.
זמן הריצה של Foo(n)
הוא
O
(
n
3
)
{\displaystyle \displaystyle O(n^{3})}
.
אנא כתוב מימוש יעיל לפונקציה Find-Num-In-Range(A, a, b)
, המקבלת:
מערך ממויין A
של מספרים שלמים חיוביים
מספר שלם חיובי a
מספר שלם חיובי b
גדול ממש מa
ומחזירה את מספר האיברים בA
שכל אחד מהם נמצא בתחום
[
a
,
b
)
{\displaystyle \displaystyle [a,b)}
.
דוגמה:
אם
A = [1, 2, 4, 5, 99 , 11999]
,
אז
Find-Num-In-Range(A, 3, 99)
תחזיר 2 (יש שני איברים בתחום).
הערה : אנא מצא מימוש הפועל בזמן לוגריתמי באורך המערך.
להלן הפונקציה Merge
המקבלת שני מערכים ממויינים :
# Merge.
# Takes two sorted arrays (L, R).
# Returns a sorted array of L ∪ R.
Merge ( L , R )
1 Merged = Make - Array ( Length ( L ) + Length ( R ) )
2 l = r = m = 1
3 while l <= Length ( L ) or r <= Length ( R )
4 if r > Length ( R )
5 Merged [ m ++ ] = L [ l ++ ]
6 else if l > Length ( L )
7 Merged [ m ++ ] = R [ r ++ ]
8 else if L [ l ] < R [ r ]
9 Merged [ m ++ ] = L [ l ++ ]
10 else
11 Merged [ m ++ ] = R [ r ++ ]
12 return Merged
אנא הוכח שהפונקציה מחזירה מערך ממויין המכיל את איחוד ערכי מערכי הכניסה, ונתח את סיבוכיות הפונקציה.
אנא הוכח אחד מחסמי האינטגרלים הבאים (שתי ההוכחות דומות מאד זו לזו):
אם
f
(
n
)
{\displaystyle \displaystyle f(n)}
מונוטונית לא יורדת, אז
∫
m
−
1
n
f
(
x
)
d
x
≤
∑
i
=
m
n
[
f
(
i
)
]
≤
∫
m
n
+
1
f
(
x
)
d
x
{\displaystyle \displaystyle \int _{m-1}^{n}f(x)dx\leq \sum _{i=m}^{n}[f(i)]\leq \int _{m}^{n+1}f(x)dx}
אם
f
(
n
)
{\displaystyle \displaystyle f(n)}
מונוטונית לא עולה, אז
∫
m
n
+
1
f
(
x
)
d
x
≤
∑
i
=
m
n
[
f
(
i
)
]
≤
∫
m
−
1
n
f
(
x
)
d
x
{\displaystyle \displaystyle \int _{m}^{n+1}f(x)dx\leq \sum _{i=m}^{n}[f(i)]\leq \int _{m-1}^{n}f(x)dx}
f
(
n
)
{\displaystyle \displaystyle f(n)}
ו
g
(
n
)
{\displaystyle \displaystyle g(n)}
הן פונקציות חיוביות ממש,
והגבול
l
i
m
n
→
∞
[
f
(
n
)
/
g
(
n
)
]
{\displaystyle \displaystyle lim_{n\rightarrow \infty }[f(n)/g(n)]}
קיים ושווה ל
l
i
m
n
→
∞
[
f
(
n
)
/
g
(
n
)
]
=
c
{\displaystyle \displaystyle lim_{n\rightarrow \infty }[f(n)/g(n)]=c}
. אנא הוכח או
הפרך את הטענה הבאה: אם
c
=
0
{\displaystyle \displaystyle c=0}
או
c
=
∞
{\displaystyle \displaystyle c=\infty }
, אז
f
(
n
)
≠
Θ
(
g
(
n
)
)
{\displaystyle \displaystyle f(n)\neq \Theta (g(n))}
.
אנא הוכח או הפרך כ"א מהכללים הבאים:
f
(
n
)
+
g
(
n
)
=
Θ
(
max
{
f
(
n
)
,
g
(
n
)
}
)
{\displaystyle \displaystyle f(n)+g(n)=\Theta (\max\{f(n),g(n)\})}
f
(
n
)
−
g
(
n
)
=
Θ
(
max
{
f
(
n
)
,
g
(
n
)
}
)
{\displaystyle \displaystyle f(n)-g(n)=\Theta (\max\{f(n),g(n)\})}
f
(
n
)
{\displaystyle \displaystyle f(n)}
היא פונקציה חיובית ממש, מונוטונית עולה, ושואפת לאינסוף. אנא הוכח שקיימת פונקציה
g
(
n
)
{\displaystyle \displaystyle g(n)}
כך שמתקיים
f
(
n
)
=
Θ
(
g
(
n
)
)
{\displaystyle \displaystyle f(n)=\Theta (g(n))}
אבל הגבול
f
(
n
)
/
g
(
n
)
{\displaystyle \displaystyle f(n)/g(n)}
אינו קיים.