算法

  1. 定义：特定计算模型下，旨在解决某一信息处理问题而设计的一个指令序列
  2. 要素：
    • 输入：待处理的信息
    • 输出：经处理的信息
    • 正确性：的确可以解决特定的问题
    • 确定性：算法应该可以描述为有若干语义明确的基本操作组成的指令序列
    • 可行性：每一个基本操作在对应的计算模型中均可兑现，且在常数时间内完成
    • 有穷性：对于任何输出，经过有穷次基本操作，都可以得到输出
  3. 注意：程序未必是算法 (死循环 / 栈溢出)

算法分析

  1. 好的算法：效率，正确，健壮，可读
  2. 分析内容：正确性，成本

复杂度度量

  1. 分析特定实例 -> 分析一类问题
  2. 分析最好情况 -> 分析最坏情况 (big-O)
  3. 实验统计 -> 客观标准
  4. 图灵机，随机存储机等计算模型：算法运行时间 $\propto$ 算法需要执行的基本操作次数
    为度量算法性能提供了准确的尺度

大 O 记号

Mathematics is more in need of good notations than of new theorems.

–Alan Turing

  1. TuringMachine 等计算模型：度量的直尺
    O 记号：直尺的刻度
  2. 定性与定量的折中 (不求甚解)
    关心成本的增长速度
    渐进分析：当 n >> 2 后，规模为 n 的输入，计算成本如何增长
  3. 定义
    若存在 $c > 0$，使得对任何 $n \gg 2$ 都有
    $T(n) \leq c \cdot f(n)$，可认为在 $n$ 足够大时，$f(n)$ 给出了 $T(n)$ 增长速度的渐进上界
    可以记为 $T(n) = O(f(n))$
  4. 性质
    • 常系数可忽略：$O(c \cdot f(n)) = O(f(n))$
    • 低次项可忽略：$O(n^a+n^b) = O(n^a)$

其他记号

  1. $\Omega$ 记号 (渐近下界)：$T(n) \ge c \cdot f(n)$
  2. $\Theta$ 记号 (确界)：$c1 > c2 > 0$ 时, $c1 \cdot f(n) > T(n) > c2 \cdot f(n)$

空间复杂度

  1. 以上三种渐进记号同样适用于空间复杂度
  2. 空间复杂度一般不计入原始输入本身所占用的空间
  3. 我们一般仅需考虑时间复杂度，而不必对空间复杂度进行专门的考查
    原因：每次基本操作所涉及的存储空间都不会超过常数规模，
    所以整个算法使用的存储空间的规模不会超过算法需要执行的基本操作次数
    而算法运行时间 $\propto$ 算法需要执行的基本操作次数 $\ge$ 算法存储空间，
    故一个算法的时间复杂度是其空间复杂度的天然上界，考查时间复杂度后一般不必考察空间复杂度
  4. 某些情况下，考察时间复杂度也有其特定的意义