שימו לב:
*נא להגיש רק את שאלות 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}
נתונות שתי פונקציות:
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)}
![{\displaystyle \displaystyle \int _{m-1}^{n}f(x)dx\leq \sum _{i=m}^{n}[f(i)]\leq \int _{m}^{n+1}f(x)dx}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e904a3978702831a002b072b8c21e07caa6717db)
![{\displaystyle \displaystyle \int _{m}^{n+1}f(x)dx\leq \sum _{i=m}^{n}[f(i)]\leq \int _{m-1}^{n}f(x)dx}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7aa781e7f8a129153032b83188b464a60655dfad)
![{\displaystyle \displaystyle lim_{n\rightarrow \infty }[f(n)/g(n)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/971efbdf38937635e591fa8ac3369f06ba0dd2b7)
![{\displaystyle \displaystyle lim_{n\rightarrow \infty }[f(n)/g(n)]=c}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d385365b624da8a7d544b2d96dcb9e115248ed9b)
