高级算法课程相关
T
(
n
)
=
a
T
(
n
b
)
+
O
(
n
d
)
=
{
O
(
n
d
l
o
g
b
n
)
,
a
=
b
d
O
(
n
d
)
,
a
<
b
d
O
(
n
l
o
g
b
a
)
,
a
>
b
d
T
(
n
)
=
a
T
(
n
b
)
+
O
(
n
d
)
为证明这种通用的递归关系的时间复杂度。不妨假设，
T
(
n
)
=
a
T
(
n
b
)
+
c
⋅
n
d
,
T
(
1
)
=
c
T(n)=aT\left(\frac{n}{b}\right) + c \cdot n^d,\;\; T(1)=c
T(n)=aT(bn)+c⋅nd,T(1)=c
由递归树展开(实际上也是按公式定义一层层展开)，
T
(
n
)
=
a
T
(
n
b
)
+
c
⋅
n
d
=
a
(
a
T
(
n
b
2
)
+
c
⋅
(
n
b
)
d
)
+
c
⋅
n
d
=
a
2
T
(
n
b
2
)
+
c
⋅
n
d
⋅
a
b
d
+
c
⋅
n
d
=
.
.
.
=
a
l
o
g
b
n
T
(
1
)
+
c
⋅
n
d
⋅
(
a
b
d
)
l
o
g
b
n
−
1
+
.
.
.
+
c
⋅
n
d
⋅
a
b
d
+
c
⋅
n
d
=
c
⋅
a
l
o
g
b
n
+
c
⋅
n
d
⋅
(
a
b
d
)
l
o
g
b
n
−
1
+
.
.
.
+
c
⋅
n
d
⋅
a
b
d
+
c
⋅
n
d
=
c
⋅
n
d
⋅
(
a
b
d
)
l
o
g
b
n
+
c
⋅
n
d
⋅
(
a
b
d
)
l
o
g
b
n
−
1
+
.
.
.
+
c
⋅
n
d
⋅
a
b
d
+
c
⋅
n
d
=
c
⋅
n
d
∑
t
=
0
l
o
g
b
n
(
a
b
d
)
t
分析右边的求和公式，
f
(
n
)
=
∑
t
=
0
n
x
t
,
x
为
常
数
,
即
上
述
的
a
b
d
f(n)=\sum\limits_{t=0}^nx^t,\;x为常数,即上述的\frac{a}{b^d}
f(n)=t=0∑nxt,x为常数,即上述的bda