我们先拿出 2021 csp-s 程序题中一道看着就头大的程序题，要求分析 solve1 的复杂度。


设 $T(n)$ 表示数组长度为 $n$ 时的复杂度（即 $m-h+1=n$）。$T(1)=1$，根据 return solve1(h,j)+solve1(j+1,m); 可知，$T(n)=2\ast T(n/2)+1$（分别做两个 solve1，加起来并 return 的时间）。推导：
$T(n)=2\times T(n/2)+1$
$=2\times (2\times T(n/2^2)+1)+1$
$=2^2\times T(n/2^2)+2+1$
$=2^2\times (2\times T(n/2^3)+1)+2+1$
$=2^3\times T(n/2^3)+2^2+2+1$
(这里默认所有 $\log$ 都是下取整）
括号中的 $n/2^k$ 在 $k={\log }_{2}n$ 时无法继续分解，为最终情况。大概找到规律了，开始写出通用式子。
$T(n)=2^{{\log }_{2}n}\times T(n/2^{{\log }_{2}n})+2^{{\log }_2(n-1)}+2^{{\log }_2(n-2)}+\cdots +2+1$
因为 $T(n/2^{{\log }_{2}n})$ 是一个小于 $2$ 的常数，在时间复杂度计算中忽略，$T(n)=2^{{\log }_2(n+1)}-1=2\times 2^{{\log }_{2}n}-1=2n-1$。
总结：递归题时间复杂度计算要关注调用函数的地方，写出时间复杂度的递推式，再归纳为易计算的代数式。
solve2 请读者尝试自己计算吧！（后续更新讲解）

---

今天作业从黑板的最上端一直写到最下端（可是我们才刚上初二啊，至于吗…），四个副科（物，化，道法，历史） + 三个主科 = 一个崩溃到明天想集体不上学的班级 + 一群充满了谩骂声的学生。此处我并不知道为什么我还能准备初赛，如果不是看了会儿 ES 续上命，本人的灵魂已经飞往天外了。