算法分析基础¶

chapter 2 Algorithm Analysis 算法分析¶

1. 定义¶

An algorithm is a finite set of instructions that,if followed,accomplishes a particular task.

算法是计算机可执行的实现特定任务的有限条指令的集合

它满足：
- input
- output
- definiteness
- finiteness
- effectiveness
程序不是必须finite的（e.g 操作系统）

2. 算法分析内容：¶

运行时间：与机器和编译器以及数据集大小有关
时间&空间复杂度：只与算法有关
假设：
- 指令按顺序执行
- 所有指令都很简单，只消耗一个相同的时间单元
- 数据规模固定，执行空间无限
通常会分析 \(T_{\mathrm{avg}}(N)\)(平均情况)和 \(T_{\mathrm{worst}}(N)\)(最差情况)，其中\(N\)为输入数据规模（可以有多个输入，对应N为多元）

3. Asymptotic Notation(渐进符号)¶

为了预测在N趋于无穷时算法步骤的增长速度

大 \(O\): \(T(N) = O(f(N))\)，如果存在大于0的常数 \(c\) 和 \(n_0\) 使得当 \(N\geq n_0\) 时 \(T(N)\leq c\cdot f(N)\)
- 渐进上界，即 \(T(N)\) 的阶不会高于 \(f(N)\)（增长比 \(f(N)\) 慢或相同，<=）
大 \(\Omega\): \(T(N) = \Omega(g(N))\)，如果存在大于0的常数 \(c\) 和 \(n_0\) 使得当 \(N\geq n_0\) 时 \(T(N)\geq c\cdot g(N)\)
- 渐进下界，即 \(T(N)\) 的阶不会低于 \(f(N)\)（增长比 \(f(N)\) 快或相同，>=）
大 \(\Theta\): \(T(N) = \Theta(h(N))\)，当且仅当 \(T(N) = O(h(N))\) 且 \(T(N) = \Omega(h(N))\)
- 渐进紧确界，即 \(T(N)\) 需要与 \(h(N)\) 同阶（增长速度相同 =）
小 \(o\): \(T(N) = o(p(N))\)，当 \(T(N) = O(p(N))\) 且 \(T(N)\ne \Theta(p(N))\) 时
- 非渐进紧确上界（\(T(N)\) 增长比 \(p(N)\) 慢，<）
小 \(\omega\): \(T(N) = \omega(p(N))\)，当 \(T(N) = \Omega(q(N))\) 且 \(T(N)\ne \Theta(q(N))\) 时
- 非渐进紧确下界（\(T(N)\) 增长比 \(q(N)\) 快，>）

主定理

Master Theorom：

假设有递推关系 \(T(n)=aT(\frac{n}{b})+f(n)\)，则：

如果存在正的常数 \(\epsilon\)，使得 \(f(n)=\Omicron(n^ {\log_{b}a-\epsilon})\)，则 \(T(n)=\Theta(n^ {\log_{b}a})\)
如果存在非负常数 \(\epsilon\)，使得 \(f(n)=\Omega(n^ {\log_{b}a+\epsilon})\)，且存在常数 \(c<1\) 使得对于充分大的 \(n\) 有 \(af(\frac{n}{b})\leq cf(n)\)，则 \(T(n)=\Theta(f(n))\)
如果存在非负常数 \(k\)，使得 \(f(n)=\Theta(n^ {\log_{b}a}\log^ {k}n)\)，则 \(T(n)=\Theta(n^ {\log_{b}a}\log^ {k+1}n)\)

规则：
- 若\(T_1(N)\) = \(O(f(N))\), \(T_2(N) = O(g(N))\):
  - \(T_1(N)\) + \(T_2(N)\) = \(\mathrm{max}(O(f(N)),O(g(N)))\),
  - \(T_1(N)\cdot T_2(N) = O(f(N)\cdot g(N))\)
- 若 \(T(N)\)为最高次为\(k\)次的关于N的多项式，则\(T(N) = \Theta((N^k))\)
- 对于任意常数\(k\),均有\(\log^kN = O(N)\)
- 具体而言：
  - for loop: 内部语句最长时间（包括for的边界条件判断）乘以循环次数
  - nested for loop: 各个for loop 逐次相乘
  - if_else: 不超过判断条件时间与最耗时语块时间之和

例：最大子序列和问题¶

O(N³)¶

直接枚举开头结尾，并计算中间子序列和：

int MaxSubsequenceSum(const int a[], int N) {
    int res = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = i; j < N; ++j) {
            int now = 0;
            for (k = i; k <= j; ++k) {
                now += a[k];
            }
            res = max(res, now);
        }
    }
    return res;
}

O(N²)¶

同样枚举开头结尾，不过动态计算子序列和，省去最内层循环

int MaxSubsequenceSum(const int a[], int N) {
    int res = 0;
    for (int i = 0; i < N; ++i) {
        int now = 0;
        for (int j = i; j < N; ++j) {
            now += a[j];
            res = max(res, now);
        }
    }
    return res;
    }

O(NlogN)¶

使用分治算法

\[ \begin{align*} T(N) &= 2T(N/2)+cN,\quad T(1) = O(1) \\ &= 2\left(2T(N/2^2)+cN/2\right)+cN \\ &= 2^kO(1) + ckN\qquad\text{where }N/2^k=1 \\ &= O(N\log N) \end{align*} \]

O(N)¶

动态规划思想

int MaxSubsequenceSum(const int a[], int N) {
    int res = 0, now = 0;
    for (int i = 0; i < N; ++i) {
        now += a[i];
        res = max(res, now);
        now = max(now, 0);
    }
    return res;
}

对数复杂度相关¶

对分查找：\(\Omicron(\log(N))\)
欧几里得算法：\(\Omicron(\log(N))\)，因为 \(\text{if}\;m>n,\;\text{then}\;m\;\text{mod}\;n<m/2\)
gcd
```
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}
```

快速幂：\(\Omicron(\log(N))\)，即二进制取幂

非递归实现递归实现

long long binPow(long long a, long long b)
{
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

long long binPow(long long a, long long b)
{
    if (0 == b) return 1;
    long long res = binPow(a, b / 2);
    if (b % 2) {
        return res * res * a;
    } else {
        return res * res;
    }
}

最后更新: 2024年10月2日 14:45:20
创建日期: 2024年3月9日 08:53:42