算法分析

算法衡量：

• 假设：指令序列化执行，每条指令执行1个时间单元，内存无限
• 指标：时间，空间
  • 最坏时间复杂性 \(T_{worst}(N)\)：找到时间上界
  • 平均时间复杂性 \(T_{avg}(N)\)
• 比较方法：
  1. 实际运行时间 clock()
     • 问题：时间粒度太大 解决：多次运行
     • 问题：计算机性能差异
  2. 理论分析执行次数
     • 忽略常数，分析量级

例 内外循环交换

void add(int a[][MAX_SIZE], int b[][MAX_SIZE], int c[][MAX_SIZE], int rows, int cols) {
    int i, j;
    for (int i = 0; i < rows; i++)    /*rows + 1*/
        for (int j = 0; j < cols; j++)    /*rows(cols + 1)*/
            c[i][j] = a[i][j] + b[i][j];    /*rows * cols*/
}

\(T(rows,cols)=2rows\cdot cols+2rows+1\)

当\(rows>\!\!>cols\)时，交换内外循环

渐进分析：分析大概趋势，即\(\exists n_0,\forall N>n_0,T_{p1}(N)>T_{p2}(N)\)

• 记号：\(O,\Omega,\Theta,o\)
  • 上界：\(T(N)=O(f(N))\Leftrightarrow \exists c,n_0>0,\forall N\geqslant n_0, T(N)\leqslant c\cdot f(N)\)
  • 下界：\(T(N)=\Omega(f(N))\Leftrightarrow \exists c,n_0>0,\forall N\geqslant n_0, T(N)\geqslant c\cdot f(N)\)
  • 上下界：\(T(N)=\Theta(f(N))\Leftrightarrow T(N)=O(f(N))\land T(N)=\Omega(f(N))\)
  • 真上界：\(T(N)=o(f(N))\Leftrightarrow T(N)=O(f(N))\land T(N)\not=\Omega(f(N))\)
• 运算法则:
  • 若\(T_1(N)=O(f(N)),T_2(N)=O(g(N))\)，则\(T_1(N)+T_2(N)=\max(O(f(N)),O(g(N)))\) \(T_1(N)*T_2(N)=O(f(N))*O(g(N))\)
  • 若\(T(N)\in\mathbb P_k[N]\)，则\(T(N)=\Theta(N^k)\)
  • \(\forall k, \log^k N=O(N)\)

例

void add(int a[][MAX_SIZE], int b[][MAX_SIZE], int c[][MAX_SIZE], int rows, int cols) {
    int i, j;
    for (int i = 0; i < rows; i++)    /*Θ(rows)*/
        for (int j = 0; j < cols; j++)    /*Θ(rows·cols)*/
            c[i][j] = a[i][j] + b[i][j];    /*Θ(rows·cols)*/
}

\(T(rows,cols)=\Theta(rows\cdot cols)\)

复杂度计算规则：

• 循环：迭代次数 \(\times\) 被循环语句执行次数
• 多重循环：\(\prod\) 迭代次数 \(\times\) 被循环语句执行次数
• 连续语句：相加（即取最大值）
• 条件：条件判断时间 + 执行时长最长分支的执行时间
• 递归：利用数学归纳法