מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
T
(
n
)
=
Θ
(
n
log
2
(
3
)
)
{\displaystyle \displaystyle T(n)=\Theta (n^{\log _{2}(3)})}
משפט המאסטר .
נפרוש את הנוסחה:
T
(
n
)
=
{\displaystyle \displaystyle T(n)=}
T
(
n
−
1
)
+
log
(
n
)
=
{\displaystyle \displaystyle T(n-1)+\log(n)=}
T
(
n
−
2
)
+
log
(
n
−
1
)
+
log
(
n
)
=
{\displaystyle \displaystyle T(n-2)+\log(n-1)+\log(n)=}
T
(
n
−
3
)
+
log
(
n
−
2
)
+
log
(
n
−
1
)
+
log
(
n
)
=
{\displaystyle \displaystyle T(n-3)+\log(n-2)+\log(n-1)+\log(n)=}
⋯
{\displaystyle \displaystyle \cdots }
∑
i
=
1
n
[
log
(
i
)
]
=
{\displaystyle \displaystyle \sum _{i=1}^{n}[\log(i)]=}
Θ
(
n
⋅
log
(
n
)
)
.
{\displaystyle \displaystyle \Theta (n\cdot \log(n)).}
טורים שימושיים .)
נגדיר
α
′
=
1
−
α
{\displaystyle \displaystyle \alpha '=1-\alpha }
α
<
α
′
{\displaystyle \displaystyle \alpha <\alpha '}
עץ הפרישה. בעץ זה, לכל אחד מהצמתים המצויירים שני ילדים: אם הצומת מתאים לגודל
n
′
{\displaystyle \displaystyle n'}
α
n
′
{\displaystyle \displaystyle \alpha n'}
α
′
n
′
{\displaystyle \displaystyle \alpha 'n'}
α
′
=
1
−
α
{\displaystyle \displaystyle \alpha '=1-\alpha }
h
m
i
n
{\displaystyle \displaystyle h_{min}}
h
max
{\displaystyle \displaystyle h_{\max }}
קל לראות שכל רמה מלאה בעץ תורמת
Θ
(
n
)
{\displaystyle \displaystyle \Theta (n)}
Θ
(
n
)
{\displaystyle \displaystyle \Theta (n)}
Θ
(
α
n
)
+
Θ
(
α
′
n
)
=
Θ
(
n
)
{\displaystyle \displaystyle \Theta (\alpha n)+\Theta (\alpha 'n)=\Theta (n)}
Θ
(
α
2
n
)
+
Θ
(
α
α
′
n
)
+
Θ
(
α
′
α
n
)
+
Θ
(
α
′
2
n
)
=
Θ
(
α
n
)
+
Θ
(
α
′
n
)
Θ
(
n
)
{\displaystyle \displaystyle \Theta (\alpha ^{2}n)+\Theta (\alpha \alpha 'n)+\Theta (\alpha '\alpha n)+\Theta (\alpha '^{2}n)=\Theta (\alpha n)+\Theta (\alpha 'n)\Theta (n)}
אפשר לראות, לכן, ש
T
(
n
)
{\displaystyle \displaystyle T(n)}
h
m
i
n
⋅
Θ
(
n
)
{\displaystyle \displaystyle h_{min}\cdot \Theta (n)}
h
max
⋅
Θ
(
n
)
{\displaystyle \displaystyle h_{\max }\cdot \Theta (n)}
h
m
i
n
=
Θ
(
log
(
n
)
)
{\displaystyle \displaystyle h_{min}=\Theta (\log(n))}
h
max
=
Θ
(
log
(
n
)
)
{\displaystyle \displaystyle h_{\max }=\Theta (\log(n))}
T
(
n
)
=
Θ
(
n
⋅
log
(
n
)
)
{\displaystyle \displaystyle T(n)=\Theta (n\cdot \log(n))}
![{\displaystyle \displaystyle \sum _{i=1}^{n}[\log(i)]=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11350a4916c587a55c257aed7daf80732188d2d9)
