coolliyong.github.io

时间复杂度和大 O 表示法

算法引入

需求
如果 a+b+c = 1000 且 a^2+b^2 = c^2 (a,b,c 为自然数),如何求出 a,b,c 可能的组合
先上一段代码

function numGroup() {
  for (let a = 0; a < 1000; a++) {
    for (let b = 0; b < 1000; b++) {
      for (let c = 0; c < 1000; c++) {
        if (a + b + c === 1000 && a * a + b * b === c * c) {
          console.log('组合', a, b, c)
        }
      }
    }
  }
}
numGroup()

结果

组合 0 500 500
组合 200 375 425
组合 375 200 425
组合 500 0 500

花费时间
2.443 seconds 执行次数 1000 _ 1000 _ 1000

比对了 2.443 才得出来，且这个时间和次数会随着数字的增加而成线性增长，由此可见，这是一个糟糕的解决方案

改进版

function numGroup() {
  let c
  for (let a = 0; a < 1000; a++) {
    for (let b = 0; b < 1000; b++) {
      c = 1000 - a - b
      if (a * a + b * b === c * c) {
        console.log('组合', a, b, c)
      }
    }
  }
}

结果

组合 0 500 500
组合 200 375 425
组合 375 200 425
组合 500 0 500

花费时间
0.091 seconds 执行次数 1000 * 1000

时间从2.443S降到了0.09S 优于上面的代码，因此我们可以得出算法的执行时间可以反应出算法的效率，即算法的优劣

注：单纯依靠运行的时间来比较算法的优劣并不是绝对的,可能在不同的机器、环境下，计算的结果并不一致

时间复杂度和大 O 表示法

我们假定计算机执行算法每一个基本操作的时间是一个固定时间单位，那么有多少个基本操作就会花费多少时间单位，算法对于不同的机器环境而言，确切的单位时间是不同的，但是对于算法进行多少个基本操作(即花费多少时间单位)在规模数量级上确实相同的,因此可以忽略机器环境的影响而客观的反应算法的时间效率

每台机器执行的总时间不同，但是执行单位运行数量大体相同

对于算法的时间效率，我们可以用“大 O 计法来表示”

“大 O 计法”：对于单调的整体函数 f，如果存在一个整体函数 g 和实常数 c>0,使得对于充分大的 n 总有 f(n)<=o*g(n),就是函数 g 是 f 的一个渐近函数(忽略常数),计为 f(n)=O(g(n)),在趋向无穷的极限意义下，函数 f 的增长速度受到函数 g 的约束，亦即函数 f 与函数 g 的特征相似.

时间复杂度：假设存在函数 g，使得算法 A 在处理规模为 n 的问题上使用时间为 T(n) = O(g(n)),则 O(g(n))为算法 A 的渐近时间复杂度，简称时间复杂度,记为 T（n）

第一段代码 T = 1000 _ 1000 _ 1000 假设需求结果改成求 2000 T = 2000 _ 2000 _ 2000 得出 T(n) = n^3

最坏时间复杂度

分析算法时，存在几种可能的考虑

算法完成工作量最少需要多少基本操作，即最优时间复杂度
算法完成工作量最多需要多少基本操作，即最坏时间复杂度
算法完成工作量平均需要多少基本操作，即平均时间复杂度

我们主要关注算法的最坏情况是通过最坏时间复杂度。

时间复杂度的几条基本计算规则

基本操作，只有常数项，认为其时间复杂度是 O(1)
顺序操作，时间复杂度按加法进行计算
循环结构，时间复杂度按乘法进行计算
分支结构，时间复杂度取最大值
判断一个算法的效率时，旺旺只需要关注操作数量的最高次项，其他次要项和常数项可以忽略
没有特殊说明时，我们分析算法的时间复杂度都是最坏时间复杂度

线性时间 T（n） = O(n)

搬砖 1 块需要 1 分钟搬砖 10 块需要 10 分钟搬砖 50 块需要 50 分钟

问：搬砖 N 块砖需要多久

T(n) = O(n)

对数时间 logO(n)

有 10000 块砖，偷个懒，每天搬一半

第一天搬 10000 / 2
第二天搬 10000 / 4
第三天搬 10000 / 8 第四天搬 10000 / 16

问：那需要多天搬完呢?

T(n) = O(log n)

常数时间 T（n） = 2

大家一天只吃一顿午饭吃一顿午饭需要一个小时

问一天吃午饭需要多少时间？

T(n) = 1

多项式 T（n） = 0.5n^2 + 0.5n

汽车百米加速第 1S 跑了 1 米第 2 秒跑了 2 米第 3 秒跑了 3 米第 10 秒跑了 10 米

问这 10 秒一共跑了多少米

1+2+3+4+... + 10 = (1+n)*n/2 = 0.5n^2 + 0.5n

一些常见的大 O 运行时间

O(log n)，也叫对数时间，这样的算法包括二分查找。
O(n)，也叫线性时间，这样的算法包括简单查找。
O(n * log n)，这样的算法包括快速排序——一种速度较快的排序算法。
O(n2)，选择排序——一种速度较慢的排序算法。
O(n!)，旅行商问题的解决方案——一种非常慢的算法。

渐进时间复杂度

有了基本操作执行次数的函数 T（n），是否就可以分析和比较一段代码的运行时间了呢？还是有一定的困难。
比如算法 A 的相对时间是 T（n）= 100n，算法 B 的相对时间是 T（n）= 5n^2，这两个到底谁的运行时间更长一些？这就要看 n 的取值了。
所以，这时候有了渐进时间复杂度（asymptotic time complexity）的概念，官方的定义如下：
1. 若存在函数 f（n），使得当 n 趋近于无穷大时，T（n）/ f（n）的极限值为不等于零的常数，则称 f（n）是 T（n）的同数量级函数。
2. 记作 T（n）= O（f（n）），称 O（f（n））为算法的渐进时间复杂度，简称时间复杂度。
3. 渐进时间复杂度用大写 O 来表示，所以也被称为大 O 表示法。

直白的讲：时间复杂度就是把时间规模 T（n）简化为一个数量级，这个数量级可以是 n,n^2,n^3 等等

如何推导时间复杂度呢？

如果运行时间是常数，用常数1表示
只保留时间函数中的最高阶数。
如果最高阶数存在，则省去最高阶项前面的系数。

常数时间、对数时间、线性时间、多项式时间究竟谁用时更长，谁节省时间呢？稍微思考一下就可以得出结论：

O（1）< O（logn）< O（n）< O（n^2）