算法分析

所谓算法，即特定计算模型下，旨在解决特定问题的指令序列。具体来说，其包含以下要素：

• 输入：待处理的信息（问题）
• 输出：经处理的信息（答案）
• 正确性：的确可以解决指定的问题
• 确定性：任一算法都可以描述为一个由基本操作组成的序列
• 可行性：每一基本操作都可实现，且在常数时间内完成
• 有穷性：对于任何输入，经有穷次基本操作，都可以得到输出

一个好的算法包含以下特性：

• 正确：符合语法，能够编译、链接
• 健壮：能辨别不合法的输入并做适当处理，而不致非正常退出
• 可读：结构化 + 准确命名 + 注释 + ...
• 效率：速度尽可能快；存储空间尽可能少

在本系列文章中，我们重点关注效率方面。

算法分析主要包括两个方面：

• 正确性：算法功能与问题要求一致？
• 成本：运行时间 + 所需存储空间

通过挖掘算法的不变性和单调性可以证明算法的正确性。

大 O 记号

大 O 记号（big-O notation）：\(T(n) = O(f(n))\) iff \(\exists c > 0\)，当 \(n >> 2\) 后，有 \(T(n) < c \times f(n)\)

根据以上定义，我们可以得出关于大 O 记号的两个重要处理手法：

• 常系数可忽略：\(O(f(n)) = O(c \times f(n))\)
• 低次项可忽略：\(O(n^a + n^b) = O(n^a), a > b > 0\)

除此之外，还有以下记号：

• \(T(n) = \Omega(f(n))\)：\(\exists c > 0\)，当 \(n >> 2\) 后，有 \(T(n) > c \times f(n)\)
• \(T(n) = \Theta(f(n))\)：\(\exists c_1 > c_2 > 0\)，当 \(n >> 2\) 后，有 \(c_1 \times f(n) > T(n) > c_2 \times f(n)\)

根据大 O 记号，我们可以把时间复杂度分为以下几类：

• \(O(1)\)：常数（constant function）复杂度，这类算法的效率最高，不含转向（循环、调用、递归等），必顺序执行，即是 \(O(1)\)
• \(O(logn)\)：对数复杂度，常底数无所谓，常数次幂也无所谓，这类算法非常有效，复杂度无限接近于常数。
• \(O(n^c)\)：多项式（polynomial function）复杂度，其中一个特例是线性（\(O(n)\)）复杂度，这类算法的效率通常认为已可令人满意。
• \(O(2^n)\)：指数（exponential function）复杂度，这类算法的计算成本增长极快，通常被认为不可忍受。

从 \(O(n^c)\) 到 \(O(2^n)\)，是从有效算法到无效算法的分水岭。很多问题的 \(O(2^n)\) 算法往往显而易见，然而，设计出 \(O(n^c)\) 算法却极其不易，甚至，有时注定地只能是徒劳无功。

在最好和最坏情况下，相差极其悬殊的算法，叫输入敏感（input-sensitive）的算法，也就是说，它的复杂度具体是多少，与输入时候数据的配置紧密的相关。