复杂度分析

参考：《算法导论》、复杂度 - OI Wiki (oi-wiki.org)、一文弄懂算法的时间和空间复杂度分析 - 知乎 (zhihu.com)、算法讲解之复杂度分析 - 知乎 (zhihu.com)、算法的时间复杂度和空间复杂度-总结_zolalad的博客-CSDN博客_时间复杂度

算法复杂度分析的阶段：

• 事前分析
• 事后测试

时间复杂度

时间复杂度是指执行这个算法所需要的计算工作量，其复杂度反映了程序执行时间**「随输入规模增长而增长的量级」**，时间复杂度越高，算法越慢

术语

• 频率计数：某条语句的执行次数

• $f(n)$ ：所有代码的执行总次数，类似于 $T(n)$ ，但是是 $T(n)$ 没有加渐进符号($O之类$)的形式

• $g(n)$：在事前分析时确定的一个关于 $n$ 的函数，与具体的语言和机器无关

• 时间频度 $T(n)$：一个算法中所有语句的执行次数，是最坏情况运行时间函数，$T(n)$ 的规律称为时间复杂度

  • 所有代码的执行总时间 $T(n)$ 和每行代码的执行次数 $n$ （问题的规模）之间的关系是： $T(n)=O(f(n))$

• 时间复杂度中 $log$ 和 $lg$ 都指 $lo{g}_2$

• 渐进记号：

  • （1）【渐进上界】上界函数 $O(n)$ ：对应最坏情况

    • 如果算法用 $n$ 值不变的同一类数据在某台机器上运行时，所用的时间总是小于 $|g(n)|$ 的一个常数倍。所以 $g(n)$ 是计算时间 $T(n)$ 的一个上界函数，$f(n)$ 的最大数量级是 $g(n)$ 。
    • O(g(n))={f(n):存在正常量c和n0,使得对所有的n≥n0,都有0≤f(n)≤cg(n)}O(g(n))=\{f(n):存在正常量c和n_0,使得对所有的n \geq n_0,都有 0 \leq f(n) \leq cg(n) \}O(g(n))={f(n):存在正常量c和n0​,使得对所有的n≥n0​,都有0≤f(n)≤cg(n)}

    （2）【渐进下界】下界函数 $\Omega (n)$ ：对应最好情况

    • 如果算法用 $n$ 值不变的同一类数据在某台机器上运行时，所用的时间总是大于 $|g(n)|$ 的一个常数倍。所以 $g(n)$ 是计算时间 $T(n)$ 的一个下界函数，$f(n)$ 的最小数量级是 $g(n)$ 。
    • Ω(g(n))={f(n):存在正常量c和n0,使得对所有的n≥n0,都有0≤cg(n)≤f(n)}Ω(g(n))=\{f(n):存在正常量c和n_0,使得对所有的n \geq n_0,都有 0 \leq cg(n) \leq f(n) \}Ω(g(n))={f(n):存在正常量c和n0​,使得对所有的n≥n0​,都有0≤cg(n)≤f(n)}

    （2）【渐进确界】平均函数 $\Theta (n)$ ：对应平均情况

    • Θ(g(n))={f(n):存在正常量c1,c2和n0,使得对所有的n≥n0,都有0≤c1g(n)≤f(n)≤c2g(n)}Θ(g(n))=\{f(n):存在正常量c_1,c_2和n_0,使得对所有的n \geq n_0,都有0 \leq c_1g(n) \leq f(n) \leq c_2g(n) \}Θ(g(n))={f(n):存在正常量c1​,c2​和n0​,使得对所有的n≥n0​,都有0≤c1​g(n)≤f(n)≤c2​g(n)}
    • 即当且仅当有 $T(n)=\Omega (g(n))$ 且 $T(n)=O(g(n))$ 时，有 $T(n)=\Theta (g(n))$

时间复杂度只关注最高数量级，且与系数也没有关系

时间复杂度计算方法

时间复杂度一般按照最坏情况（比如排序时让数据是逆序的）计算。

时间复杂度分析有一个基本的法则，就是四则运算法则。

• 加法法则：如果算法的代码是平行增加的，那么就需要加上相应的时间复杂度。
• 乘法法则：如果算法的代码增加的是循环内的嵌套或者函数的嵌套，那么就需要乘上相应的时间复杂度。循环需要由内向外分析
• 减法法则：如果是去掉算法中平行的代码，就需要减掉相应的时间复杂度。
• 除法法则：如果是去掉嵌套内的循环或函数，就需要除去相应的时间复杂度。

即：总结：时间复杂度分析的基本策略是：从内向外分析，从最深层开始分析。如果遇到函数调用，就要深入函数进行分析

• 常数项忽略（只有常数项时就是 $O(1)$）
• 只保留最高阶项
• 与最高阶项相乘的系数忽略
• 常数级操作：$O(1)$
• 1层循环：$O(n)$，$n$ 为循环的次数
• 多层循环：$O(n_1\times n_2\times n_3\times ...)$，$n_i$ 是第 $i$ 层循环的次数【由内向外分析】
• 条件判断语句：总的时间复杂度等于其中 时间复杂度最大的路径 的时间复杂度
• 顺序执行语句：总的时间复杂度等于其中最大的时间复杂度

主定理(Master Theorem)

特别的，对于递归算法，可以使用递归树或者主定理求解时间复杂度。

主定理适用于求解如下递归式算法的时间复杂度：

$T(n)=aT(n/b)+f(n)$

其中：

• $n$ 是当前问题规模大小；
• $a$ 是原问题的子问题个数；
• $n/b$ 是每个子问题的大小，这里假设每个子问题有相同的规模大小；
• $f(n)$ 是将原问题分解成子问题和将子问题的解合并成原问题的解的时间（还有常数操作的时间）。

使用情况：

1. If f(n) = O(n logb a−ε ) for some constant > 0, then T (n) = Θ(n logb a ).
2. If f(n) = Θ(n logb a logk n) with1 k ≥ 0, then T (n) = Θ(n logb a logk+1 n).
3. If f(n) = Ω(n logb a+ε ) with > 0, and f(n) satisfies the regularity condition, then T (n) = Θ(f(n)). Regularity condition: af(n/b) ≤ cf(n) for some constant c < 1 and all sufficiently large n

常见的时间复杂度

• 多项式时间：$O(1)<O(lo{g}_{2}n)<O(n)<O(nlo{g}_{2}n)<O(n^2)<O(n^3)<O(n^m)$，对应 P（Polynomial,多项式）类问题

• 指数时间：$O(2^n)<O(n!)<O(n^n)$，对应NP（Non-Deterministic Polynomial, 非确定多项式）问题

$O(1)<O(lo{g}_{2}n)<O(n)<O(nlo{g}_{2}n)<O(n^2)<O(n^3)<O(n^m)\dots <O(2^n)<O(n!)<O(n^n)$

注意：当规模 $n$ 很大时，一定存在常数 $m$，使得 $2^n>n^m$

空间复杂度

空间复杂度是对一个算法在运行过程中**临时占用存储空间大小的量度，所谓的临时占用存储空间指的就是代码中「辅助变量所占用的空间」，它包括为参数表中「形参变量」分配的存储空间和为在函数体中定义的「局部变量」**分配的存储空间两个部分。【全局变量不属于空间复杂度考虑范围】

空间复杂度使用 $S(n)=O(f(n))$ 来定义，其中 $n$ 为问题的规模。

$O(1)$ 的空间复杂度是指算法消耗的空间不随数据规模的增大而增大。