我们先拿出 2021 csp-s 程序题中一道看着就头大的程序题，要求分析 solve1 的复杂度。
设
T(n)
\operatorname{T(n)}
T(n) 表示数组长度为
n
n
n 时的复杂度（即
m
−
h
+
1
=
n
m-h+1=n
m−h+1=n）。
T
(
1
)
=
1
T(1)=1
T(1)=1，根据 return solve1(h,j)+solve1(j+1,m); 可知，
T(n)
=
2
∗
T
(
n
/
2
)
+
1
\operatorname{T(n)}=2*\operatorname{T}(n/2)+1
T(n)=2∗T(n/2)+1（分别做两个 solve1，加起来并 return 的时间）。推导：
T(n)
=
2
×
T(n/2)
+
1
\operatorname{T(n)}=2\times \operatorname{T(n/2)}+1
T(n)=2×T(n/2)+1
=
2
×
(
2
×
T
(
n
/
2
2
)
+
1
)
+
1
=2\times(2\times \operatorname{T}(n/2^2)+1)+1
=2×(2×T(n/22)+1)+1
=
2
2
×
T
(
n
/
2
2
)
+
2
+
1
=2^2\times \operatorname{T}(n/2^2)+2+1
=22×T(n/22)+2+1
=
2
2
×
(
2
×
T
(
n
/
2
3
)
+
1
)
+
2
+
1
=2^2\times(2\times\operatorname{T}(n/2^3)+1)+2+1
=22×(2×T(n/23)+1)+2+1
=
2
3
×
T
(
n
/
2
3
)
+
2
2
+
2
+
1
=2^3\times \operatorname{T}(n/2^3)+2^2+2+1
=23×T(n/23)+22+2+1
(这里默认所有
log
\log
log 都是下取整）
括号中的
n
/
2
k
n/2^k
n/2k 在
k
=
log
2
n
k=\log_{2}n
k=log2n 时无法继续分解，为最终情况。大概找到规律了，开始写出通用式子。
T
(
n
)
=
2
log
2
n
×
T
(
n
/
2
log
2
n
)
+
2
log
2
(
n
−
1
)
+
2
log
2
(
n
−
2
)
+
⋯
+
2
+
1
\operatorname{T}(n)=2^{ \log_2n}\times \operatorname{T}(n/2^{ \log_2n})+2^{ \log_2(n-1)}+2^{ \log_2(n-2)}+\dots+2+1
T(n)=2log2n×T(n/2log2n)+2log2(n−1)+2log2(n−2)+⋯+2+1
因为
T
(
n
/
2
log
2
n
)
\operatorname{T}(n/2^{ \log_2n})
T(n/2log2n) 是一个小于
2
2
2 的常数，在时间复杂度计算中忽略，
T
(
n
)
=
2
log
2
(
n
+
1
)
−
1
=
2
×
2
log
2
n
−
1
=
2
n
−
1
\operatorname{T}(n)=2^{ \log_2(n+1)}-1=2\times2^{ \log_2n}-1=2n-1
T(n)=2log2(n+1)−1=2×2log2n−1=2n−1。
总结：递归题时间复杂度计算要关注调用函数的地方，写出时间复杂度的递推式，再归纳为易计算的代数式。
solve2 请读者尝试自己计算吧！（后续更新讲解）
今天作业从黑板的最上端一直写到最下端（可是我们才刚上初二啊，至于吗…），四个副科（物，化，道法，历史） + 三个主科 = 一个崩溃到明天想集体不上学的班级 + 一群充满了谩骂声的学生。此处我并不知道为什么我还能准备初赛，如果不是看了会儿 ES 续上命，本人的灵魂已经飞往天外了。
标签：log,递归,复杂度,times,计算,2n,2log2,operatorname From： https://blog.csdn.net/2401_84512298/article/details/142219585