常见的复杂度

复杂度分为两种：

• 时间复杂度
• 空间复杂度

常见时间复杂度

时间复杂度衡量的是一种变化趋势。随着 n 增大，整个时间花费的 变化趋势 是怎样的。

1. O(1)
2. O(logn)
3. O(n)
4. O(nlogn)
5. O(n²)
6. O(2ⁿ)
7. O(n!)

上面的这几种复杂度，从上往下，随着 n 的增大，时间花费都不相同。越上面的，时间变化趋势越平缓性能越优；越往下面，时间增长趋势越陡峭，性能就越低。

O(1)

let n = 100
console.log(n)

O(1) 的时间复杂度不会随着 n 的变化，运行时间有什么增加。

O(logn)

for (let i = 1; i < n; i *= 2) {
  // ...
}

因为每次迭代都是将 i 翻两倍，循环的次数是对数级别的。因此时间复杂度为 O(logn)

假设 n 是 8，就会循环 3 次。

O(n)

for (let i = 1; i <= n; i++) {
  //...
}

上面的代码，n 为多少，就会循环多少次，因此时间复杂度为 O(n) 级别。

假设 n 是 8，就会循环 8 次。

O(nlogn)

for (let i = 0; i <= n; i++) {
  let j = 1
  while (j < n) {
    j *= 2
  }
}

O(n²)

for (let i = 1; i <= n; i++) {
  for (let j = 1; j <= n; j++) {
    // ...
  }
}

依此类推，假设有三层循环，那么时间复杂度就是 O(n^3)

O(2^n)

比如递归算法。每多展开一层，运算的个数也就会翻 2 倍，以 2 的幂次方的规律增长。

课堂思考🤔

如果两个 for 循环不是嵌套的，而是并列的，时间复杂度是多少？

for (let i = 1; i <= n; i++) {
  // ...
}
for (let j = 1; j <= n; j++) {
  // ...
}

答案：最终的时间复杂度仍然为 O(n)。在大O表示法中，只有高阶的项才决定了算法最终的时间复杂度。

O(n) + O(logn) = O(n)

O(n²) + O(n) = O(n²)

常见的空间复杂度

衡量的是随着 n 的增长，所使用的内存空间的一个增长趋势。

1. O(1)

let i = 1
i++
let j = 2
j++
n = 10
console.log(n)

2. O(n)

let arr = new Array(n)

这里 n 有多大，就决定为数组开辟的内存空间有多大。

3. O(n^2)

let arr = new Array(n)
for (let i = 0; i < n; i++) {
  arr[i] = new Array(n)
}

🤔了解时间和空间复杂度的好处？

了解了时间和空间复杂度之后，以后在写代码的时候，就会自然而然的去想一下自己写的这段代码的性能如何。

需求：计算从 1 加到 n 的和

let sum = 0
for (let i = 1; i <= n; i++) {
  sum += i
}

上面这种解法，时间复杂度为 O(n)，但是我们现在换一种算法，采用数学里面等差数列的求和公式：

let sum = (n * (n + 1)) / 2

上面的解法，时间复杂度就从 O(n) 下降到了 O(1)

-EOF-