时间复杂度 Big O

参考资料

1. https://www.youtube.com/watch?v=JgWm6sQwS_I
2. https://www.bilibili.com/video/BV1y14y1G7Cr?p=11&vd_source=6e32730b05dc719c9f21598867bef69d

我们使用大写英文字母 O 来表示算法的时间复杂度，常见的时间复杂度有：

1. O(1)
2. O(log n)
3. O(n)
4. O(n^2)
5. O(2^n)

时间复杂度的推导

现在有一个问题需要我们解决，计算从 1 加到 n 的总和

我们首先会想到：可以使用循环来解决这个问题呀！

function sumUp(n) {
  let result = 0
  for (let i = 1; i <= n; i++)
    result += i

  return result
}

数学好的同学可能会想到：哦，我们可以使用数学公式来计算

function sumUp(n) {
  return (n / 2) * (n + 1)
}

在以上两种解法中我们会发现，第一个函数会在数字很大的时候使用的时间很长，而第二个公式无论数字有多大，它都只执行一次。

我们如何使用O来表达两者的时间复杂度呢？

1. 我们要先使用数学公式表达这个函数执行的次数

在这里我们假设执行每一步所需的时间都一致

function sumUp(n) {
  let result = 0
  for (let i = 1; i <= n; i++)
    result += i

  return result
}

给定一个 n = 1，我们来观察每一行执行的次数

function sumUp(n) {
  let result = 0 // 执行1次
  for (let i = 1; i <= n; i++) { // 执行1次
    result += i // 执行1次
  }
  return result // 执行1次
}

给定 n = 3，我们再来观察执行次数

function sumUp(n) {
  let result = 0 // 执行1次
  for (let i = 1; i <= n; i++) { // 执行1次
    result += i // 执行3次
  }
  return result // 执行1次
}

给定 n = n，我们再来观察执行次数

function sumUp(n) {
  let result = 0 // 执行1次
  for (let i = 1; i <= n; i++) { // 执行1次
    result += i // 执行n次
  }
  return result // 执行1次
}

我们使用一个数学公式来表示执行的时间

T = 1 + 1 + n + 1 = 3 + n = 3 + 1 * n
我们这里不关心具体的次数，将其替换为变量
T =  a + b * n

2. 我们要找到增长最快的变量

我们会发现，上面增长最快的变量是 T = b * n

3. 我们去除这个变量的系数

去除这个变量的系数后，我们会得到 T = n

4. 将得到的变量放置到 O()的括号中

所以这个算法的时间复杂度是 O(n)

示例

有上面的例子后，我们推导一下使用数学公式的算法的时间复杂度

function sumUp(n) {
  return (n / 2) * (n + 1)
}

变量	执行次数
1	1
3	1
n	1

T = 1

所以我们得到的该算法的时间复杂度是O(1)