算法分析¶
一个算法(algorithm) 是为了实现特定任务的一个有限条指令的集合
算法满足这些性质：
- Input
- Output
- Definiteness
- Finiteness
- Effectiveness
Note: program 可以不 finite(e.g. 操作系统)
分析内容¶
- 运行时间：与机器、编译器有关
- 时间 & 空间复杂度：与机器、编译器无关
假设：
- 指令按顺序执行
- 每条指令是简单的，只需要一个时间单位执行
- 数据规模是给定的，而空间是无限的
通常我们需要分析 \(T_{avg}(N) \& T_{worst}(N)\), \(N\) 是输入规模（可以有多个输入）
渐进符号¶
定义¶
大 \(O\) 表示法 \(T(N) = O(f(N))\)，如果存在常数 \(c\) 和 \(n_0\)使得当 \(N\geq n_0\) 时 \(T(N)\leq c\cdot f(N)\)
渐进上界，即 \(T(N)\) 的阶不会高于 \(f(N)\)（增长比 \(f(N)\) 慢或相同，\(\leq\)）大 \(\Omega\) 表示法 \(T(N) = \Omega(g(N))\)，如果存在常数 \(c\) 和 \(n_0\)使得当 \(N\geq n_0\) 时 \(T(N)\geq c\cdot f(N)\)
渐进下界，即 \(T(N)\) 的阶不会低于 \(f(N)\)（增长比 \(f(N)\) 快或相同，\(\geq\)）大 \(\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)\neq \Theta(p(N))\) 时成立 非渐进紧确上界，（即 \(T(N)\) 增长比 \(p(N)\)慢，\(<\)）
小 \(w\) 表示法 \(T(N) = w(p(N))\)，当 \(T(N)=\Omega(p(N))\) 且 \(T(N)\neq \Theta(p(N))\) 时成立 非渐进紧确下界，（即 \(T(N)\) 增长比 \(p(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)\cdot T_2(N)=O(f(N)\cdot g(N))\)
- 若 \(T(N)\) 是最高次数为 k 次的多项式，那么 \(T(N)=\Theta ((N^k))\)
- 对于任意常数 \(k\), 都有 \(\log^kN=O(N)\)，这说明对增长非常缓慢。
- 分析时的规则
- for loop
运行时间是循环内部语句的最长时间（包括 for 边界判断）乘循环的次数 - 嵌套 for loop
运行时间是各个 for loop 的运行时间逐次相乘 - 连续执行的语句
相加 - if else
运行时间不会超过判断时间加上用时最多的语句块的时间
- for loop
创建日期: 2022年11月22日 14:15:00