大O复杂度表示法

如何用肉眼判断一段代码的执行时间呢?

第一个例子

  1. function cal(n: number): number {
  2.     let sum = 0;
  3.     let i = 1;
  4.     for(; i<= n; ++i){
  5.         sum = sum + i;
  6.     } 
  8.     return sum; 
  9. }
  • 这里我们只是粗略地进行估计, 假设每行的执行时间都一样, 为 unit_time
  • 第 2, 3 行代码分别需要执行 1 次, 共 2 次
  • 第 4, 5 行, 都需要重复 n 次, 共 2n 次
  • 那么一共需要执行的时间为 (2n + 2 ) * unit_time

第二个例子

  1. function cal(n: number): number{
  2.   let sum = 0;
  3.   let i = 1; 
  4.   let j = 1;
  5.   for(; i<=n; ++i){
  6.     j = 1;
  7.     for(; j<=n; ++j){
  8.       sum = sum + i * j
  9.     }
  10.   }
  11. }
  • 假设每次执行语句, cpu 花费的时间是一致的, 为 unit_time
  • 第2, 3, 4 行代码会执行一次, 共计 3
  • 第 5, 6 行代码会被循环 n 次, 共计 2n, 第七行开启的 for 循环会循环 n 次
    • 第 7, 8 行代码所在的 for 循环语句循环 n 次, 共计 n n 2
  • 总计执行次数 3 + 2n + 2n*n
  • 总计执行时间为 (3 + 2n + 2nn) unit_time

大O表示法 T(n) = O(fn))

  • 我们用一个公式来 表达运行一段代码所消耗的时间:

  • T(n) 表示代码执行消耗的总时间.

    • n 表示 数据规模的大小.

  • f(n) 表示代码执行的总次数

  • O 表示一个比值, O 表示代码的执行时间 与 执行次数 ( f(n) 表达式的结果 ) 是正比

  • 这是一种记法, 表达代码执行的次数, 我们并不关心实际结果, 也不关心 O 的大小.

  • 对于第一个例子 T(n) = O(2n+2), 对于第二个例子 T(n) = O(2n² + 2n + 3), 这就是 大 O 时间复杂度表示法.

对于 时间复杂度 我们关注的什么?

执行时间的随着数据规模增大的增长趋势

  • 大 O 时间复杂度实际上并不具体表示代码真正的执行时间, 而是表示代码执行时间随着 数据规模变化的增长趋势, 这个趋势被称为 渐进时间复杂度, 简称 时间复杂度.

影响增长系数的最大量级

  • 对于这个公式来说, n 可以是非常大的数字, 这时公式中的低阶, 常量 和 系数, 都不足以左右增长趋势, 所以可以忽略, 我们只需要记录一个最大量级.

  • 对于第一个例子, 最大的量级是 n, 可以记为 T(n) = O(n)

  • 对于第二个例子, 最大的量级是 n² , 因此可以记为 T(n) = O(n²)

时间复杂度的分析方法

1. 只关注循环执行次数最多的一段代码

  • 我们在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了

    2. 加法法则：总复杂度等于量级最大的那段代码的复杂度

  • 总的时间复杂度就等于量级最大的那段代码的时间复杂度。那我们将这个规律抽象成公式就是：

  • 如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n))).

3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)T2(n)=O(f(n))O(g(n))=O(f(n)*g(n)).

几种常见时间复杂度实例分析

image.jpeg

  • 对于上述的几种复杂度量级, 我们可以粗略地将其分为两种: 多项式量级, 非多项式量级.

非多项式量级

  • 非多项式量级只有两个: O(2^n)和O(n!)
  • 非多项式量级的算法问题被称作 NP (Non-Deterministic Polynomial)
  • 当数据规模 n 变大时, 非多项式量级 算法 的执行时间会急剧增加. 所以, 非多项式时间复杂度的算法是低效的算法. 所以, 我们主要关注的是几种常见的多项式时间复杂度.

多项式量级