复杂度分析

$O(1)$

  1. 分类：一般地，仅含一次或常数次基本操作的算法
    此类算法通常不含循环，分支，子程序调用
  2. 效率最高

$O((logn)^c)$

  1. 不必写出 $\log$ 的底数，因为 $\log_{a}{n} = \log_{a}{b} \cdot \log_{b}{n}$
    同理常数次幂不必写，因为 $\log_{a}{n^c} = c\log_{a}{n}$
    对数多项式类型的复杂度可以忽略低次项
  2. 复杂度无限接近于常数，效率第二高

$O(n^c)$

  1. $n$ 的多项式类型的复杂度可以忽略所有低次项
  2. $O(n) \sim O(n^2)$是编程习题主要覆盖的范围
  3. 效率第三高，比较令人满意

$O(2^n)$

  1. 成本增长快，难解
  2. $O(n^c) \rightarrow O(2^n)$ 是从有效算法 $\rightarrow$ 无效算法的分水岭
  3. 某些问题算法最优解就是 $O(2^n)$ 了，不存在 $O(n^c)$ 的算法
    如 2-Subset 问题就是 NP-complete

算法分析

  1. 任务：正确性(不变性 && 单调性) + 复杂度
  2. 复杂度分析的主要方法
    • 迭代：级数求和
    • 递归：递归跟踪 + 递推方程
    • 猜测 + 验证

级数

  • 算数级数：与末项平方同阶

$$T(n) = 1+2+3+…+n = \frac{n(n+1)}{2} = O(n^2) $$

  • 幂级数：比幂次高一阶

$$T(n) = 1^c+2^c+ … +n^c = O(n^{c+1})$$

  • 等比级数：与末项同阶

$$T(n) = a^0+a^1+a^2+…+a^n = O(a^n)$$

  • 收敛级数

$$T(n) = O(1)$$

  • 调和级数

$$T(n) = 1+\frac{1}{2}+\frac{1}{3}+…+\frac{1}{n} = \Theta(logn)$$

  • 对数级数

$$T(n) = log1+log2+…+logn = log(n!) = \Theta(nlogn)$$

循环

  • 二重循环(1)的复杂度 (类比 j-i 坐标系中矩形的面积)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        O1Operation(i, j);
    }
}

$$T(n) = \sum_{i=0}^{n-1}n = n \times n = O(n^2)$$

  • 二重循环(2)的复杂度 (类比 j-i 坐标系中三角形的面积)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        O1Operation(i, j);
    }
}

$$T(n) = \sum_{i=0}^{n-1}i = 0+1+…+(n-1) = \frac{n(n-1)}{2} = O(n^2)$$

  • 二重循环(3)的复杂度 (类比 $\frac{j}{c}$-i 坐标系中三角形的面积)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j += c) {
        O1Operation(i, j);
    }
}

$$T(n) = O(n^2)$$

  • 二重循环(4)的复杂度 (几何级数)
for (int i = 1; i < n; i *= 2) {
    for (int j = 0; j < i; j ++) {
        O1Operation(i, j);
    }
}

$$T(n) = 1+2+4+…+2^{\log_{2}{n-1}} = \sum_{k=0}^{\log_{2}{(n-1)}}2^k (let \ k = \log_{2}{i})= O(n)$$

  • 二重循环(5)的复杂度 (几何级数)
for (int i = 0; i < n; i ++) {
    for (int j = 1; j < i; j += j) {
        O1Operation(i, j);
    }
}

$$T(n)=0+0+1+2 \times 2+3 \times 4+4 \times 8…=\sum_{k=0…logn}^{}(k \cdot 2^{k-1})=O(\log_{}{n} \cdot2^{\log_{}{n}})=O(n\log_{}{n})$$