עריכה
אנא הוכח או הפרך את הטענות הבאות:
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}
נכון.
הוכחה: נבחר
c
=
1
{\displaystyle \displaystyle c=1}
n
0
=
100
{\displaystyle \displaystyle n_{0}=100}
∀
n
≥
100
80
≤
1
⋅
3
⋅
n
{\displaystyle \displaystyle \forall _{n\geq 100}80\leq 1\cdot 3\cdot n}
נכון.
הוכחה: נבחר
c
=
2
1008
{\displaystyle \displaystyle c=2^{1008}}
n
0
=
1
{\displaystyle \displaystyle n_{0}=1}
∀
n
≥
1
2
n
+
1003
+
30
=
2
1003
⋅
2
n
+
30
≤
2
1008
⋅
2
n
{\displaystyle \displaystyle \forall _{n\geq 1}2^{n+1003}+30=2^{1003}\cdot 2^{n}+30\leq 2^{1008}\cdot 2^{n}}
נכון.
הוכחה: נבחר
c
=
3
{\displaystyle \displaystyle c=3}
n
0
=
1
{\displaystyle \displaystyle n_{0}=1}
∀
n
≥
1
2
⋅
n
+
7
≤
3
⋅
(
2
⋅
n
+
3
)
=
6
⋅
n
+
9
{\displaystyle \displaystyle \forall _{n\geq 1}2\cdot n+7\leq 3\cdot (2\cdot n+3)=6\cdot n+9}
לא נכון.
הוכחה: נניח בשלילה שהטענה נכונה, ולכן עבור
c
>
0
{\displaystyle \displaystyle c>0}
n
0
>
0
{\displaystyle \displaystyle n_{0}>0}
∀
n
≥
n
0
3
⋅
n
≤
c
⋅
1
{\displaystyle \displaystyle \forall _{n\geq n_{0}}3\cdot n\leq c\cdot 1}
n
=
n
0
+
⌈
c
⌉
,
{\displaystyle \displaystyle n=n_{0}+\left\lceil c\right\rceil ,}
(
3
⋅
n
)
|
n
0
+
⌈
c
⌉
=
3
⋅
n
0
+
3
⋅
⌈
c
⌉
≤
{\displaystyle \displaystyle (3\cdot n)|^{n_{0}+\left\lceil c\right\rceil }=3\cdot n_{0}+3\cdot \left\lceil c\right\rceil \leq }
(
c
⋅
1
)
|
n
0
+
⌈
c
⌉
=
c
,
{\displaystyle \displaystyle (c\cdot 1)|^{n_{0}+\left\lceil c\right\rceil }=c,}
נכון.
הוכחה: באופן כללי,
log
b
(
a
)
=
log
c
(
a
)
/
log
c
(
b
)
{\displaystyle \displaystyle \log _{b}(a)=\log _{c}(a)/\log _{c}(b)}
אנא הוכח את כלל האדיטיביות ל
Ω
{\displaystyle \displaystyle \Omega }
f
(
n
)
,
g
(
n
)
{\displaystyle \displaystyle f(n),g(n)}
Ω
(
f
(
n
)
)
+
Ω
(
g
(
n
)
)
=
Ω
(
f
(
n
)
+
g
(
n
)
)
{\displaystyle \displaystyle \Omega (f(n))+\Omega (g(n))=\Omega (f(n)+g(n))}
ההוכחה דומה למדי להוכחת האדיטיביות שראינו בהרצאה :
הוכחה: (1) עפ"י ההגדרה:
f
1
(
n
)
=
Ω
(
f
(
n
)
)
{\displaystyle \displaystyle f_{1}(n)=\Omega (f(n))}
n
≥
n
0
,
f
{\displaystyle \displaystyle n\geq n_{0,f}}
f
1
(
n
)
≥
c
f
⋅
f
(
n
)
{\displaystyle \displaystyle f_{1}(n)\geq c_{f}\cdot f(n)}
c
f
,
n
0
,
f
>
0
{\displaystyle \displaystyle c_{f},n_{0,f}>0}
g
1
(
n
)
=
Ω
(
g
(
n
)
)
{\displaystyle \displaystyle g_{1}(n)=\Omega (g(n))}
n
≥
n
0
,
g
{\displaystyle \displaystyle n\geq n_{0,g}}
g
1
(
n
)
≥
g
⋅
g
(
n
)
{\displaystyle \displaystyle g_{1}(n)\geq _{g}\cdot g(n)}
c
g
,
n
0
,
g
>
0
{\displaystyle \displaystyle c_{g},n_{0,g}>0}
לכן:
לכל
n
≥
max
{
n
0
,
f
,
n
0
,
g
}
{\displaystyle \displaystyle n\geq \max\{n_{0,f},n_{0,g}\}}
f
1
(
n
)
≥
max
{
c
f
,
c
g
}
⋅
f
(
n
)
{\displaystyle \displaystyle f_{1}(n)\geq \max\{c_{f},c_{g}\}\cdot f(n)}
לכל
n
≥
max
{
n
0
,
f
,
n
0
,
g
}
{\displaystyle \displaystyle n\geq \max\{n_{0,f},n_{0,g}\}}
g
1
(
n
)
≥
max
{
c
f
,
c
g
}
⋅
g
(
n
)
{\displaystyle \displaystyle g_{1}(n)\geq \max\{c_{f},c_{g}\}\cdot g(n)}
מקבלים את התוצאה ע"י חיבור שני האי-שוויונים האחרונים.
אנא הוכח את טרנזיטיביות ל
Ω
{\displaystyle \displaystyle \Omega }
f
(
n
)
,
g
(
n
)
{\displaystyle \displaystyle f(n),g(n)}
f
(
n
)
=
Ω
(
g
(
n
)
)
∧
g
(
n
)
=
Ω
(
h
(
n
)
)
⇒
f
(
n
)
=
Ω
(
h
(
n
)
)
{\displaystyle \displaystyle f(n)=\Omega (g(n))\wedge g(n)=\Omega (h(n))\Rightarrow f(n)=\Omega (h(n))}
ההוכחה דומה למדי להוכחת הטרנזיטיביות שראינו :
(1) עפ"י ההגדרה:
f
(
n
)
=
Ω
(
g
(
n
)
)
{\displaystyle \displaystyle f(n)=\Omega (g(n))}
n
≥
n
0
,
f
{\displaystyle \displaystyle n\geq n_{0,f}}
f
(
n
)
≥
c
f
⋅
g
(
n
)
{\displaystyle \displaystyle f(n)\geq c_{f}\cdot g(n)}
n
0
,
f
,
c
f
>
0
{\displaystyle \displaystyle n_{0,f},c_{f}>0}
g
(
n
)
=
Ω
(
h
(
n
)
)
{\displaystyle \displaystyle g(n)=\Omega (h(n))}
n
≥
n
0
,
g
{\displaystyle \displaystyle n\geq n_{0,g}}
g
(
n
)
≥
c
g
⋅
g
(
n
)
{\displaystyle \displaystyle g(n)\geq c_{g}\cdot g(n)}
n
0
,
g
,
c
g
>
0
{\displaystyle \displaystyle n_{0,g},c_{g}>0}
לכן:
לכל
n
≥
max
{
n
0
,
f
,
n
0
,
g
}
{\displaystyle \displaystyle n\geq \max\{n_{0,f},n_{0,g}\}}
f
(
n
)
≥
c
f
⋅
f
(
n
)
{\displaystyle \displaystyle f(n)\geq c_{f}\cdot f(n)}
לכל
n
≥
max
{
n
0
,
f
,
n
0
,
g
}
{\displaystyle \displaystyle n\geq \max\{n_{0,f},n_{0,g}\}}
g
(
n
)
≥
c
g
⋅
g
(
n
)
{\displaystyle \displaystyle g(n)\geq c_{g}\cdot g(n)}
מקבלים את התוצאה ע"י הצבת שני האי-שוויונים האחרונים אחד בשני:
לכל
n
≥
max
{
n
0
,
f
,
n
0
,
g
}
{\displaystyle \displaystyle n\geq \max\{n_{0,f},n_{0,g}\}}
f
(
n
)
≥
c
f
⋅
c
g
⋅
h
(
n
)
{\displaystyle \displaystyle f(n)\geq c_{f}\cdot c_{g}\cdot h(n)}
עריכה
f
(
n
)
,
g
(
n
)
{\displaystyle \displaystyle f(n),g(n)}
f
(
n
)
=
O
(
g
(
n
)
)
⇒
g
(
n
)
=
O
(
f
(
n
)
)
{\displaystyle \displaystyle f(n)=O(g(n))\Rightarrow g(n)=O(f(n))}
f
(
n
)
+
g
(
n
)
=
Θ
(
m
i
n
{
f
(
n
)
,
g
(
n
)
}
)
{\displaystyle \displaystyle f(n)+g(n)=\Theta (min\{f(n),g(n)\})}
f
(
n
)
=
O
(
g
(
n
)
)
⇒
2
f
(
n
)
=
O
(
2
g
(
n
)
)
{\displaystyle \displaystyle f(n)=O(g(n))\Rightarrow 2^{f(n)}=O(2^{g(n)})}
f
(
n
)
+
Θ
(
f
(
n
)
)
=
Θ
(
f
(
n
)
)
{\displaystyle \displaystyle f(n)+\Theta (f(n))=\Theta (f(n))}
f
(
n
)
=
2
log
(
n
)
,
g
(
n
)
=
(
log
(
n
)
)
log
(
n
)
⇒
f
(
n
)
=
O
(
g
(
n
)
)
{\displaystyle \displaystyle f(n)=2^{\log(n)},g(n)=(\log(n))^{\log(n)}\Rightarrow f(n)=O(g(n))}
(לתזכורת,
f
(
n
)
,
g
(
n
)
{\displaystyle \displaystyle f(n),g(n)}
לא נכון. נפריך ע"י
f
(
n
)
=
n
2
,
g
(
n
)
=
n
3
{\displaystyle \displaystyle f(n)=n^{2},g(n)=n^{3}}
לא נכון. נפריך ע"י
f
(
n
)
=
n
2
,
g
(
n
)
=
n
3
{\displaystyle \displaystyle f(n)=n^{2},g(n)=n^{3}}
לא נכון. נפריך ע"י
f
(
n
)
=
2
⋅
n
,
g
(
n
)
=
n
{\displaystyle \displaystyle f(n)=2\cdot n,g(n)=n}
לכל פונקציה
g
(
n
)
=
Θ
(
f
(
n
)
)
{\displaystyle \displaystyle g(n)=\Theta (f(n))}
c
″
⋅
f
(
n
)
≤
g
(
n
)
≤
c
′
⋅
f
(
n
)
{\displaystyle \displaystyle c''\cdot f(n)\leq g(n)\leq c'\cdot f(n)}
c
″
,
c
′
>
0
{\displaystyle \displaystyle c'',c'>0}
n
0
>
0
{\displaystyle \displaystyle n_{0}>0}
n
0
{\displaystyle \displaystyle n_{0}}
(
1
+
c
″
)
⋅
f
(
n
)
≤
f
(
n
)
+
g
(
n
)
≤
(
1
+
c
′
)
⋅
f
(
n
)
,
{\displaystyle \displaystyle (1+c'')\cdot f(n)\leq f(n)+g(n)\leq (1+c')\cdot f(n),}
l
i
m
n
→
∞
[
f
(
n
)
/
g
(
n
)
]
=
0
{\displaystyle \displaystyle lim_{n\rightarrow \infty }[f(n)/g(n)]=0}
ולכן עפ"י כללי הגבולות שראינו, הטענה נכונה.
אנא הוכח או הפרך כ"א מהכללים הבאים:
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
)
+
g
(
n
)
≥
max
{
f
(
n
)
,
g
(
n
)
}
{\displaystyle \displaystyle f(n)+g(n)\geq \max\{f(n),g(n)\}}
f
(
n
)
+
g
(
n
)
≤
2
⋅
max
{
f
(
n
)
,
g
(
n
)
}
{\displaystyle \displaystyle f(n)+g(n)\leq 2\cdot \max\{f(n),g(n)\}}
ניקח
f
(
n
)
=
n
+
1
{\displaystyle \displaystyle f(n)=n+1}
g
(
n
)
=
n
{\displaystyle \displaystyle g(n)=n}
f
(
n
)
−
g
(
n
)
=
1
≠
Θ
(
n
)
=
Θ
(
max
{
f
(
n
)
,
g
(
n
)
}
)
{\displaystyle \displaystyle f(n)-g(n)=1\neq \Theta (n)=\Theta (\max\{f(n),g(n)\})}
n
2
≠
O
(
n
)
{\displaystyle \displaystyle n^{2}\neq O(n)}
1
≠
Ω
(
n
)
{\displaystyle \displaystyle 1\neq \Omega (n)}
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
)
)
{\displaystyle \displaystyle f(n)=\Theta (g(n))}
c
″
>
0
{\displaystyle \displaystyle c''>0}
c
′
>
0
{\displaystyle \displaystyle c'>0}
n
{\displaystyle \displaystyle n}
c
″
⋅
g
(
n
)
≤
f
(
n
)
≤
c
′
⋅
g
(
n
)
{\displaystyle \displaystyle c''\cdot g(n)\leq f(n)\leq c'\cdot g(n)}
g
(
n
)
{\displaystyle \displaystyle g(n)}
≤
{\displaystyle \displaystyle \leq }
c
″
≤
f
(
n
)
/
g
(
n
)
≤
c
′
{\displaystyle \displaystyle c''\leq f(n)/g(n)\leq c'}
c
″
{\displaystyle \displaystyle c''}
c
′
{\displaystyle \displaystyle c'}
עריכה
עריכה
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)}
נבנה את הפונקציה
g
(
n
)
{\displaystyle \displaystyle g(n)}
ראשית נקבע צמדים של נקודות.
נקבע
n
0
=
1
{\displaystyle \displaystyle n_{0}=1}
n
1
{\displaystyle \displaystyle n_{1}}
f
(
n
1
)
≥
2
⋅
f
(
n
0
)
{\displaystyle \displaystyle f(n_{1})\geq 2\cdot f(n_{0})}
f
(
n
)
{\displaystyle \displaystyle f(n)}
נקבע
n
2
=
n
1
+
1
{\displaystyle \displaystyle n_{2}=n_{1}+1}
n
3
{\displaystyle \displaystyle n_{3}}
f
(
n
3
)
≥
2
⋅
f
(
n
2
)
{\displaystyle \displaystyle f(n_{3})\geq 2\cdot f(n_{2})}
f
(
n
)
{\displaystyle \displaystyle f(n)}
נמשיך כך הלאה: נקבע
n
4
=
n
3
+
1
{\displaystyle \displaystyle n_{4}=n_{3}+1}
n
5
{\displaystyle \displaystyle n_{5}}
f
(
n
5
)
≥
2
⋅
f
(
n
4
{\displaystyle \displaystyle f(n_{5})\geq 2\cdot f(n_{4}}
f
(
n
)
{\displaystyle \displaystyle f(n)}
כעת נגדיר את
g
(
n
)
{\displaystyle \displaystyle g(n)}
עבור
n
0
≤
n
<
n
1
{\displaystyle \displaystyle n_{0}\leq n<n_{1}}
g
(
n
)
=
f
(
n
0
)
{\displaystyle \displaystyle g(n)=f(n_{0})}
g
(
n
1
)
=
f
(
n
1
)
/
2
{\displaystyle \displaystyle g(n_{1})=f(n_{1})/2}
עבור
n
2
≤
n
<
n
3
{\displaystyle \displaystyle n_{2}\leq n<n_{3}}
g
(
n
)
=
f
(
n
2
)
{\displaystyle \displaystyle g(n)=f(n_{2})}
g
(
n
3
)
=
f
(
n
3
)
/
2
{\displaystyle \displaystyle g(n_{3})=f(n_{3})/2}
עבור
n
4
≤
n
<
n
5
{\displaystyle \displaystyle n_{4}\leq n<n_{5}}
g
(
n
)
=
f
(
n
4
)
{\displaystyle \displaystyle g(n)=f(n_{4})}
g
(
n
5
)
=
f
(
n
5
)
/
2
{\displaystyle \displaystyle g(n_{5})=f(n_{5})/2}
g
(
n
)
{\displaystyle \displaystyle g(n)}
בכל נקודה ונקודה,
g
(
n
)
{\displaystyle \displaystyle g(n)}
f
(
n
)
{\displaystyle \displaystyle f(n)}
f
(
n
)
/
2
{\displaystyle \displaystyle f(n)/2}
g
(
n
)
=
Θ
(
f
(
n
)
)
{\displaystyle \displaystyle g(n)=\Theta (f(n))}
יש אינסוף נקודות בהן
f
(
n
)
=
g
(
n
)
{\displaystyle \displaystyle f(n)=g(n)}
g
(
n
)
=
f
(
n
)
/
2
{\displaystyle \displaystyle g(n)=f(n)/2}
f
(
n
)
/
g
(
n
)
{\displaystyle \displaystyle f(n)/g(n)}
הפונקציה
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 }
ערוך מניפולציות על איבר הטור הכללי ועל גבולות הסיכום כך שיתקבל איבר טור שאינו תלוי בגבולות הסיכום (ולכן ניתן יהיה להוציאו מחוץ לסכום).
נשתמש באותו הרעיון בו השתמשתנו כדי לנתח טור של לוגריתמים .
f
(
n
)
=
O
(
n
3
)
{\displaystyle \displaystyle f(n)=O(n^{3})}
הוכחה:
f
(
n
)
=
∑
i
=
1
n
∑
j
=
i
n
[
Θ
(
j
−
i
+
1
)
]
≤
∑
i
=
1
n
∑
j
=
1
n
[
Θ
(
n
)
]
=
Θ
(
n
3
)
{\displaystyle \displaystyle f(n)=\sum _{i=1}^{n}\sum _{j=i}^{n}[\Theta (j-i+1)]\leq \sum _{i=1}^{n}\sum _{j=1}^{n}[\Theta (n)]=\Theta (n^{3})}
כעת נראה כי
f
(
n
)
=
Ω
(
n
3
)
{\displaystyle \displaystyle f(n)=\Omega (n^{3})}
הוכחה:
f
(
n
)
=
∑
i
=
1
n
∑
j
=
i
n
[
Θ
(
j
−
i
+
1
)
]
≥
∑
i
=
1
n
/
4
∑
j
=
i
n
[
Θ
(
j
−
i
+
1
)
]
≥
∑
i
=
1
n
/
4
∑
j
=
3
n
/
4
n
[
Θ
(
j
−
i
+
1
)
]
{\displaystyle \displaystyle f(n)=\sum _{i=1}^{n}\sum _{j=i}^{n}[\Theta (j-i+1)]\geq \sum _{i=1}^{n/4}\sum _{j=i}^{n}[\Theta (j-i+1)]\geq \sum _{i=1}^{n/4}\sum _{j=3n/4}^{n}[\Theta (j-i+1)]}
i
{\displaystyle \displaystyle i}
1
,
…
,
n
/
4
{\displaystyle \displaystyle 1,\ldots ,n/4}
j
{\displaystyle \displaystyle j}
3
n
/
4
,
…
,
n
{\displaystyle \displaystyle 3n/4,\ldots ,n}
Θ
(
j
−
i
+
1
)
=
Ω
(
n
/
2
)
=
Ω
(
n
)
{\displaystyle \displaystyle \Theta (j-i+1)=\Omega (n/2)=\Omega (n)}
לכן נקבל
f
(
n
)
≥
∑
i
=
1
n
/
4
∑
j
=
3
n
/
4
n
[
Ω
(
n
)
]
=
Θ
(
n
3
)
{\displaystyle \displaystyle f(n)\geq \sum _{i=1}^{n/4}\sum _{j=3n/4}^{n}[\Omega (n)]=\Theta (n^{3})}
f
(
n
)
=
∑
i
=
1
n
∑
j
=
i
n
[
Θ
(
j
−
i
+
1
)
]
{\displaystyle \displaystyle f(n)=\sum _{i=1}^{n}\sum _{j=i}^{n}[\Theta (j-i+1)]}
נשים לב שעבור ערך
i
{\displaystyle \displaystyle i}
j
′
=
j
−
i
{\displaystyle \displaystyle j'=j-i}
∑
j
=
i
n
[
Θ
(
j
−
i
+
1
)
]
=
∑
j
′
=
0
n
−
i
[
Θ
(
j
′
+
1
)
]
=
∑
j
′
=
0
n
−
i
[
Θ
(
j
′
)
]
=
Θ
(
(
n
−
i
)
2
)
{\displaystyle \displaystyle \sum _{j=i}^{n}[\Theta (j-i+1)]=\sum _{j'=0}^{n-i}[\Theta (j'+1)]=\sum _{j'=0}^{n-i}[\Theta (j')]=\Theta ((n-i)^{2})}
נציב זאת חזרה בסכום הכפול:
f
(
n
)
=
∑
i
=
1
n
∑
j
=
i
n
[
Θ
(
j
−
i
+
1
)
]
=
∑
i
=
1
n
[
(
n
−
i
)
2
]
{\displaystyle \displaystyle f(n)=\sum _{i=1}^{n}\sum _{j=i}^{n}[\Theta (j-i+1)]=\sum _{i=1}^{n}[(n-i)^{2}]}
i
′
=
n
−
i
{\displaystyle \displaystyle i'=n-i}
f
(
n
)
=
∑
i
=
1
n
[
(
n
−
i
)
2
]
=
∑
i
′
=
0
n
−
1
[
i
′
2
]
=
Θ
(
n
3
)
{\displaystyle \displaystyle f(n)=\sum _{i=1}^{n}[(n-i)^{2}]=\sum _{i'=0}^{n-1}[i'^{2}]=\Theta (n^{3})}
עריכה
אנא הוכח ש
∑
j
=
1
h
[
2
−
j
Θ
(
j
)
]
=
Θ
(
1
)
{\displaystyle \displaystyle \sum _{j=1}^{h}[2^{-j}\Theta (j)]=\Theta (1)}
רמז
חלק את הטור לשני טורים; הראשון יהיה טור קצר המכיל מספר קבוע של איברים, והשני יהיה טור ארוך יותר. חסום את הטור השני על ידי טור הנדסי.
מצד אחד, כל טור גדול לפחות כמו איברו הראשון. מכאן נקבל:
∑
j
=
1
h
[
2
−
j
Θ
(
j
)
]
≥
[
2
−
1
Θ
(
1
)
]
≥
Θ
(
1
)
{\displaystyle \displaystyle \sum _{j=1}^{h}[2^{-j}\Theta (j)]\geq [2^{-1}\Theta (1)]\geq \Theta (1)}
Ω
(
1
)
{\displaystyle \displaystyle \Omega (1)}
מצד שני, נקבל
∑
j
=
1
h
[
2
−
j
Θ
(
j
)
]
≤
∑
j
=
1
∞
[
2
−
j
Θ
(
j
)
]
=
Θ
(
∑
j
=
1
∞
[
2
−
j
j
]
)
{\displaystyle \displaystyle \sum _{j=1}^{h}[2^{-j}\Theta (j)]\leq \sum _{j=1}^{\infty }[2^{-j}\Theta (j)]=\Theta \left(\sum _{j=1}^{\infty }[2^{-j}j]\right)}
∑
j
=
1
∞
[
2
−
j
j
]
{\displaystyle \displaystyle \sum _{j=1}^{\infty }[2^{-j}j]}
עבור ערכי
j
{\displaystyle \displaystyle j}
2
−
j
j
<
1.5
−
j
{\displaystyle \displaystyle 2^{-j}j<1.5^{-j}}
k
{\displaystyle \displaystyle k}
2
−
k
k
<
1.5
−
k
{\displaystyle \displaystyle 2^{-k}k<1.5^{-k}}
∑
j
=
1
∞
[
2
−
j
j
]
=
∑
j
=
1
k
−
1
[
2
−
j
j
]
+
∑
j
=
k
∞
[
2
−
j
j
]
≤
O
(
1
)
+
∑
j
=
k
∞
[
1.5
−
j
]
≤
O
(
1
)
+
∑
j
=
1
∞
[
1.5
−
j
]
=
O
(
1
)
+
O
(
1
)
=
O
(
1
)
{\displaystyle \displaystyle \sum _{j=1}^{\infty }[2^{-j}j]=\sum _{j=1}^{k-1}[2^{-j}j]+\sum _{j=k}^{\infty }[2^{-j}j]\leq O(1)+\sum _{j=k}^{\infty }[1.5^{-j}]\leq O(1)+\sum _{j=1}^{\infty }[1.5^{-j}]=O(1)+O(1)=O(1)}
![{\displaystyle \displaystyle lim_{n\rightarrow \infty }[f(n)/g(n)]=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/75f5c7ce360184b5af1287c05b2500050f7677b6)
![{\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)
![{\displaystyle \displaystyle \sum _{i=n_{0}}^{n}[i^{k}]=\Theta (n^{k+1})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f6a054d8be734a48a836d9547afe7af3cfe4b3d0)
![{\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 f(n)=\sum _{i=1}^{n}\sum _{j=i}^{n}[\Theta (j-i+1)]\leq \sum _{i=1}^{n}\sum _{j=1}^{n}[\Theta (n)]=\Theta (n^{3})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cac6eab16c17788f2ba9b67e6545e752060dead8)
![{\displaystyle \displaystyle f(n)=\sum _{i=1}^{n}\sum _{j=i}^{n}[\Theta (j-i+1)]\geq \sum _{i=1}^{n/4}\sum _{j=i}^{n}[\Theta (j-i+1)]\geq \sum _{i=1}^{n/4}\sum _{j=3n/4}^{n}[\Theta (j-i+1)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0057d53bbdfb938e6c0b2a3dedddd572be83b10d)
![{\displaystyle \displaystyle f(n)\geq \sum _{i=1}^{n/4}\sum _{j=3n/4}^{n}[\Omega (n)]=\Theta (n^{3})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/08f700ac32969dfe6285d940bc704f9f3c44b934)
![{\displaystyle \displaystyle f(n)=\sum _{i=1}^{n}\sum _{j=i}^{n}[\Theta (j-i+1)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7264df179bc09fa25f7437ccaf3e21eef8063496)
![{\displaystyle \displaystyle \sum _{j=i}^{n}[\Theta (j-i+1)]=\sum _{j'=0}^{n-i}[\Theta (j'+1)]=\sum _{j'=0}^{n-i}[\Theta (j')]=\Theta ((n-i)^{2})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/12ec6e1e81a61aa335c924a2d0bda46c4bbf6487)
![{\displaystyle \displaystyle f(n)=\sum _{i=1}^{n}\sum _{j=i}^{n}[\Theta (j-i+1)]=\sum _{i=1}^{n}[(n-i)^{2}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9f7f885120aa2fff189cfb0eaf914fbd4030c5e0)
![{\displaystyle \displaystyle f(n)=\sum _{i=1}^{n}[(n-i)^{2}]=\sum _{i'=0}^{n-1}[i'^{2}]=\Theta (n^{3})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1d27ffd3e248d98ebae2f00f9cd82b8c5fd357b1)
![{\displaystyle \displaystyle \sum _{j=1}^{h}[2^{-j}\Theta (j)]=\Theta (1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/42c46e0816e705ee76f01f4d3e581b9f0e015d67)
![{\displaystyle \displaystyle \sum _{j=1}^{h}[2^{-j}\Theta (j)]\geq [2^{-1}\Theta (1)]\geq \Theta (1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8a1ea6dbb6dd81377118959bcf802cc807f5c2d7)
![{\displaystyle \displaystyle \sum _{j=1}^{h}[2^{-j}\Theta (j)]\leq \sum _{j=1}^{\infty }[2^{-j}\Theta (j)]=\Theta \left(\sum _{j=1}^{\infty }[2^{-j}j]\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1838abc8daf1579bb7b58bdcbde86f3d56a64181)
![{\displaystyle \displaystyle \sum _{j=1}^{\infty }[2^{-j}j]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5d4d4f10f334b277e7e96b2df7e2f5c583e45ae5)
![{\displaystyle \displaystyle \sum _{j=1}^{\infty }[2^{-j}j]=\sum _{j=1}^{k-1}[2^{-j}j]+\sum _{j=k}^{\infty }[2^{-j}j]\leq O(1)+\sum _{j=k}^{\infty }[1.5^{-j}]\leq O(1)+\sum _{j=1}^{\infty }[1.5^{-j}]=O(1)+O(1)=O(1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4aaf962950d8f98371ad5172f53a77dd990539f8)