06多段代码复杂度合成规则

在分析一个完整的算法时，我们很少会遇到只有一个简单循环或一个简单递归的情况。
更多时候，一个算法由多个部分组成，它们可能顺序执行，可能相互嵌套，或者根据条件选择执行。这时候，我们就需要一些规则来合成这些不同部分的复杂度。

核心思想回顾

在开始学习合成规则之前，让我们快速回顾一下大O符号的核心思想：

• 关注增长趋势： 大O符号描述的是算法运行时间或空间占用随输入规模 n 增大时的增长趋势。
• 忽略常数项： $O(2n)$ 和 $O(n)$ 在 $n$ 足够大时，增长趋势是相同的，因此都简化为 $O(n)$。
• 忽略低阶项： $O(n^2+n)$ 在 $n$ 足够大时，$n^2$ 的影响远大于 $n$，因此简化为 $O(n^2)$。

相加原则（求和法则）

规则定义

如果一个算法包含多个独立的、顺序执行的代码段，那么整个算法的复杂度等于这些代码段中复杂度最高（增长最快）的那个。

规则说明

若算法A的时间复杂度为$O(f(n))$，算法B的时间复杂度为$O(g(n))$，两段代码依次执行，则整体复杂度为二者之和：
$$O(f(n))+O(g(n))$$
当$f(n)$与$g(n)$