Twierdzenie o rekurencji uniwersalnej
edytuj
Jeżeli funkcja
T
(
n
)
,
{\displaystyle T(n),}
a
⩾
1
,
b
>
1
,
n
>
0
{\displaystyle a\geqslant 1,b>1,n>0}
funkcji dodatniej
f
{\displaystyle f}
T
(
n
)
=
{
Θ
(
1
)
:
1
⩽
n
<
b
a
⋅
T
(
n
b
)
+
f
(
n
)
:
n
⩾
b
,
{\displaystyle T(n)={\begin{cases}\Theta (1)&:1\leqslant n<b\\a\cdot T\left({\frac {n}{b}}\right)+f(n)&:n\geqslant b\end{cases}},}
to:
jeżeli
f
(
n
)
=
O
(
n
log
b
a
−
ϵ
)
{\displaystyle f(n)=O(n^{\log _{b}a-\epsilon })}
ϵ
>
0
,
{\displaystyle \epsilon >0,}
T
(
n
)
=
Θ
(
n
log
b
a
)
,
{\displaystyle T(n)=\Theta (n^{\log _{b}a}),}
jeżeli
f
(
n
)
=
Θ
(
n
log
b
a
)
,
{\displaystyle f(n)=\Theta (n^{\log _{b}a}),}
T
(
n
)
=
Θ
(
n
log
b
a
⋅
log
n
)
,
{\displaystyle T(n)=\Theta (n^{\log _{b}a}\cdot \log n),}
jeżeli
f
(
n
)
=
Ω
(
n
log
b
a
+
ϵ
)
{\displaystyle f(n)=\Omega (n^{\log _{b}a+\epsilon })}
a
⋅
f
(
n
b
)
⩽
c
⋅
f
(
n
)
{\displaystyle a\cdot f\left({\frac {n}{b}}\right)\leqslant c\cdot f(n)}
c
∈
(
0
,
1
)
,
{\displaystyle c\in (0,1),}
n
,
{\displaystyle n,}
T
(
n
)
=
Θ
(
f
(
n
)
)
.
{\displaystyle T(n)=\Theta (f(n)).}
Tak zdefiniowane funkcje
T
{\displaystyle T}
dziel i zwyciężaj ” – problem o rozmiarze
n
{\displaystyle n}
a
{\displaystyle a}
n
b
,
{\displaystyle {\frac {n}{b}},}
f
{\displaystyle f}
Intuicyjna interpretacja
edytuj
Każdy z trzech przypadków rekurencji uniwersalnej sprowadza się do stwierdzenia, która z funkcji
n
log
b
a
{\displaystyle n^{\log _{b}a}}
f
{\displaystyle f}
„Dziury” rekurencji uniwersalnej
edytuj
Dowód twierdzenia o rekurencji uniwersalnej
edytuj
Dla n będących potęgą b
edytuj
Niech
n
{\displaystyle n}
potęgą liczby rzeczywistej
b
,
{\displaystyle b,}
b
>
1.
{\displaystyle b>1.}
Niech zmienne
a
,
{\displaystyle a,}
b
{\displaystyle b}
f
{\displaystyle f}
i
{\displaystyle i}
T
{\displaystyle T}
T
(
n
)
=
{
Θ
(
1
)
:
n
=
1
a
⋅
T
(
n
b
)
+
f
(
n
)
:
n
=
b
i
,
{\displaystyle T(n)={\begin{cases}\Theta (1)&:n=1\\a\cdot T\left({\frac {n}{b}}\right)+f(n)&:n=b^{i}\end{cases}},}
to
T
(
n
)
=
Θ
(
n
log
b
a
)
+
∑
j
=
0
log
b
n
−
1
a
j
⋅
f
(
n
b
j
)
.
{\displaystyle T(n)=\Theta (n^{\log _{b}a})+\sum _{j=0}^{\log _{b}n-1}a^{j}\cdot f\left({\frac {n}{b^{j}}}\right).\quad {}}
Rozważmy drzewo rekursji funkcji
T
{\displaystyle T}
Koszt korzenia drzewa wynosi
f
(
n
)
,
{\displaystyle f(n),}
a
{\displaystyle a}
f
(
n
b
)
.
{\displaystyle f\left({\frac {n}{b}}\right).}
a
{\displaystyle a}
f
(
n
b
2
)
.
{\displaystyle f\left({\frac {n}{b^{2}}}\right).}
a
2
{\displaystyle a^{2}}
2 od korzenia. Ogólniej, dla
j
<
b
{\displaystyle j<b}
a
j
{\displaystyle a^{j}}
f
(
n
b
j
)
{\displaystyle f\left({\frac {n}{b^{j}}}\right)}
j
.
{\displaystyle j.}
Koszt każdego liścia wynosi
T
(
1
)
=
Θ
(
1
)
,
{\displaystyle T(1)=\Theta (1),}
n
b
log
b
n
=
1
{\displaystyle {\frac {n}{b^{\log _{b}n}}}=1}
log
b
n
.
{\displaystyle \log _{b}n.}
a
log
b
n
=
n
log
b
a
{\displaystyle a^{\log _{b}n}=n^{\log _{b}a}}
Sumując koszty wszystkich poziomów drzewa otrzymamy równanie (*), ponieważ koszt wszystkich „poziomów” węzłów właściwych (tj. niebędących liśćmi) wynosi
∑
j
=
0
log
b
n
−
1
a
j
⋅
f
(
n
b
j
)
{\displaystyle \sum _{j=0}^{\log _{b}n-1}a^{j}\cdot f\left({\frac {n}{b^{j}}}\right)}
Θ
(
n
log
b
a
)
.
{\displaystyle \Theta (n^{\log _{b}a}).}
Niech
a
,
{\displaystyle a,}
b
{\displaystyle b}
f
{\displaystyle f}
g
{\displaystyle g}
n
{\displaystyle n}
b
{\displaystyle b}
g
(
n
)
=
∑
j
=
0
log
b
n
−
1
a
j
⋅
f
(
n
b
j
)
.
{\displaystyle g(n)=\sum _{j=0}^{\log _{b}n-1}a^{j}\cdot f\left({\frac {n}{b^{j}}}\right).}
To dla
n
{\displaystyle n}
b
{\displaystyle b}
g
{\displaystyle g}
jeżeli
f
(
n
)
=
O
(
n
log
b
a
−
ϵ
)
{\displaystyle f(n)=O(n^{\log _{b}a-\epsilon })}
ϵ
>
0
,
{\displaystyle \epsilon >0,}
g
(
n
)
=
Θ
(
n
log
b
a
)
,
{\displaystyle g(n)=\Theta (n^{\log _{b}a}),}
jeżeli
f
(
n
)
=
Θ
(
n
log
b
a
)
,
{\displaystyle f(n)=\Theta (n^{\log _{b}a}),}
g
(
n
)
=
Θ
(
n
log
b
a
⋅
log
n
)
,
{\displaystyle g(n)=\Theta (n^{\log _{b}a}\cdot \log n),}
jeżeli
f
(
n
)
=
Ω
(
n
log
b
a
+
ϵ
)
{\displaystyle f(n)=\Omega (n^{\log _{b}a+\epsilon })}
a
⋅
f
(
n
b
)
⩽
c
⋅
f
(
n
)
{\displaystyle a\cdot f\left({\frac {n}{b}}\right)\leqslant c\cdot f(n)}
c
∈
(
0
,
1
)
,
{\displaystyle c\in (0,1),}
n
,
{\displaystyle n,}
g
(
n
)
=
Θ
(
f
(
n
)
)
.
{\displaystyle g(n)=\Theta (f(n)).}
Korzystając z oszacowania z lematu 2 dla sumy (*). Dla kolejnych przypadków z lematu 2 zachodzi:
T
(
n
)
=
Θ
(
n
log
b
a
)
+
O
(
n
log
b
a
)
=
Θ
(
n
log
b
a
)
,
{\displaystyle T(n)=\Theta (n^{\log _{b}a})+O(n^{\log _{b}a})=\Theta (n^{\log _{b}a}),}
T
(
n
)
=
Θ
(
n
log
b
a
)
+
Θ
(
n
log
b
a
⋅
log
n
)
=
Θ
(
n
log
b
a
⋅
log
n
)
,
{\displaystyle T(n)=\Theta (n^{\log _{b}a})+\Theta (n^{\log _{b}a}\cdot \log n)=\Theta (n^{\log _{b}a}\cdot \log n),}
T
(
n
)
=
Θ
(
n
log
b
a
)
+
Θ
(
f
(
n
)
)
=
Θ
(
f
(
n
)
)
,
{\displaystyle T(n)=\Theta (n^{\log _{b}a})+\Theta (f(n))=\Theta (f(n)),}
f
(
n
)
=
Ω
(
n
log
b
a
+
ϵ
)
.
{\displaystyle f(n)=\Omega (n^{\log _{b}a+\epsilon }).}
Dla dowolnych n
edytuj
Dla dowolnych
n
{\displaystyle n}
b
{\displaystyle b}
n
b
{\displaystyle {\frac {n}{b}}}
⌊
n
b
⌋
{\displaystyle \left\lfloor {\frac {n}{b}}\right\rfloor }
⌈
n
b
⌉
.
{\displaystyle \left\lceil {\frac {n}{b}}\right\rceil .}
Odpowiednio górne i dolne oszacowanie dla funkcji
T
(
n
)
=
a
⋅
T
(
⌊
n
b
⌋
)
+
f
(
n
)
{\displaystyle T(n)=a\cdot T\left(\left\lfloor {\frac {n}{b}}\right\rfloor \right)+f(n)\quad {}}
i
T
(
n
)
=
a
⋅
T
(
⌈
n
b
⌉
)
+
f
(
n
)
{\displaystyle T(n)=a\cdot T\left(\left\lceil {\frac {n}{b}}\right\rceil \right)+f(n)\quad {}}
jest banalne do znalezienia, przy wykorzystaniu własności
⌊
n
b
⌋
⩾
n
b
{\displaystyle \left\lfloor {\frac {n}{b}}\right\rfloor \geqslant {\frac {n}{b}}}
⌈
n
b
⌉
⩽
n
b
.
{\displaystyle \left\lceil {\frac {n}{b}}\right\rceil \leqslant {\frac {n}{b}}.}
Równanie rekurencyjne można oszacować z góry w następujący sposób:
Niech
n
[
i
]
=
{
n
:
i
=
0
⌈
n
[
i
−
1
]
b
⌉
:
i
>
0
.
{\displaystyle n[i]={\begin{cases}n&:i=0\\\left\lceil {\frac {n[i-1]}{b}}\right\rceil &:i>0\end{cases}}.}
Wtedy schodzenie w dół rekursji oznacza jej rekurencyjne wywoływanie kolejno dla argumentów
n
[
0
]
,
n
[
1
]
,
n
[
2
]
,
…
{\displaystyle n[0],\ n[1],\ n[2],\dots }
T
(
n
)
=
T
(
⌈
n
b
⌉
)
=
T
(
⌈
⌈
n
b
⌉
b
⌉
)
=
…
{\displaystyle T(n)=T\left(\left\lceil {\frac {n}{b}}\right\rceil \right)=T\left(\left\lceil {\frac {\left\lceil {\frac {n}{b}}\right\rceil }{b}}\right\rceil \right)=\ldots }
Korzystając z nierówności
⌈
a
⌉
⩽
a
+
1
,
{\displaystyle \left\lceil a\right\rceil \leqslant a+1,}
n
[
0
]
⩽
n
,
{\displaystyle n[0]\leqslant n,}
n
[
1
]
⩽
n
b
+
1
,
{\displaystyle n[1]\leqslant {\frac {n}{b}}+1,}
n
[
2
]
⩽
n
b
2
+
1
b
+
1
,
{\displaystyle n[2]\leqslant {\frac {n}{b^{2}}}+{\frac {1}{b}}+1,}
n
[
3
]
⩽
n
b
3
+
1
b
2
+
1
b
+
1
,
{\displaystyle n[3]\leqslant {\frac {n}{b^{3}}}+{\frac {1}{b^{2}}}+{\frac {1}{b}}+1,}
…
{\displaystyle \ldots }
n
[
i
]
⩽
n
b
i
+
∑
k
=
0
i
−
1
1
b
k
<
n
b
i
+
∑
k
=
0
∞
1
b
k
=
n
b
i
+
b
b
−
1
.
{\displaystyle n[i]\leqslant {\frac {n}{b^{i}}}+\sum _{k=0}^{i-1}{\frac {1}{b^{k}}}<{\frac {n}{b^{i}}}+\sum _{k=0}^{\infty }{\frac {1}{b^{k}}}={\frac {n}{b^{i}}}+{\frac {b}{b-1}}.}
Dla
i
=
⌊
log
b
n
⌋
{\displaystyle i=\left\lfloor \log _{b}n\right\rfloor }
n
[
i
]
=
n
[
⌊
log
b
n
⌋
]
<
n
b
⌊
log
b
n
⌋
+
b
b
−
1
⩽
n
b
log
b
n
−
1
+
b
b
−
1
=
n
n
b
+
b
b
−
1
∈
O
(
1
)
.
{\displaystyle n[i]=n[\left\lfloor \log _{b}n\right\rfloor ]<{\frac {n}{b^{\left\lfloor \log _{b}n\right\rfloor }}}+{\frac {b}{b-1}}\leqslant {\frac {n}{b^{\log _{b}n-1}}}+{\frac {b}{b-1}}={\frac {n}{\frac {n}{b}}}+{\frac {b}{b-1}}\in O(1).}
Oznacza to, że dla wywołań rekursji na poziomie co najmniej
n
[
⌊
log
b
n
⌋
]
{\displaystyle n[\left\lfloor \log _{b}n\right\rfloor ]}
![{\displaystyle n[i]={\begin{cases}n&:i=0\\\left\lceil {\frac {n[i-1]}{b}}\right\rceil &:i>0\end{cases}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9b6f6665ee6998d7aea8c278a7ad10f5f0d5a142)
![{\displaystyle n[0],\ n[1],\ n[2],\dots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/84441dabf2c1c583e9fb8a5686cb50db63525474)
![{\displaystyle n[0]\leqslant n,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2d21b5de54f1b6c6c88e94787a174e346c867bf9)
![{\displaystyle n[1]\leqslant {\frac {n}{b}}+1,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/43200acd2a5ad3040af4d322eb7729f9eb4d3ed4)
![{\displaystyle n[2]\leqslant {\frac {n}{b^{2}}}+{\frac {1}{b}}+1,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/108ce74e60564d2d205d0badc3bd263e4b860b08)
![{\displaystyle n[3]\leqslant {\frac {n}{b^{3}}}+{\frac {1}{b^{2}}}+{\frac {1}{b}}+1,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/066adab9aaf5c6b130729a1071915029d5c3967d)
![{\displaystyle n[i]\leqslant {\frac {n}{b^{i}}}+\sum _{k=0}^{i-1}{\frac {1}{b^{k}}}<{\frac {n}{b^{i}}}+\sum _{k=0}^{\infty }{\frac {1}{b^{k}}}={\frac {n}{b^{i}}}+{\frac {b}{b-1}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/925d176727eb8381cc6bf9422252eceeb21ca5e1)
![{\displaystyle n[i]=n[\left\lfloor \log _{b}n\right\rfloor ]<{\frac {n}{b^{\left\lfloor \log _{b}n\right\rfloor }}}+{\frac {b}{b-1}}\leqslant {\frac {n}{b^{\log _{b}n-1}}}+{\frac {b}{b-1}}={\frac {n}{\frac {n}{b}}}+{\frac {b}{b-1}}\in O(1).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0cee49a3896367c5f54d64f69a1ef2e3aed9fa0f)
![{\displaystyle n[\left\lfloor \log _{b}n\right\rfloor ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6a3dc335863a57d394fff07733f68163821ce1ca)