Skip to content

算法分析#

一个算法(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
      运行时间不会超过判断时间加上用时最多的语句块的时间

Last update: 2023年9月27日 10:52:36
Created: 2023年9月27日 10:52:36