时间复杂度

大O符号表示法

算法的时间复杂度通常用大O符号表述，定义为 T(n) = O(f(n)) 。其中 n 表示数据规模， O(fn(n)) 表示运行算法所需要执行的指令数，和 f(n) 成正比。在数学领域，它被称作渐进复杂度。

T(n) = O(f(n)) 表示存在一个常数 C ，使得当 n 趋于正无穷时总有 T(n) <= C * f(n) 。其虽然对 f(n) 没有规定，但一般都是取尽可能简单的函数。例如，O(n² + n + 1) 、O(7n² + n + 3) 都可以用 O(n²) 表示，因为公式里的常量、系数等只是细枝末节，并不影响主干 f(n) 。

大O符号是一种算法复杂度的相对表示方式。

常见的时间复杂度量级

常见的时间复杂度：

O(1)

无论代码执行了多少行，只要没有循环等复杂结构，那代码的时间复杂度就是 O(1) ，如：

1
2
3
4
5
6

let i = 0
let j = 1

i = j
i ++
j ++

O(n)

在下面这段代码，for 循环里的代码会执行 n 遍，因此它消耗的时间随着 n 的变化而变化，因此用 O(n) 来表示它的时间复杂度：

1
2
3

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

注意：不论 i < 2n 或者 i < n / 2，都是表示为 O(n)，因为系数可被忽略。

O(n²)

当存在双重循环的时候，即把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。

1
2
3
4
5
6
7
8
9
10
11
12
13

function bubbleSort (arr) {
  const len = arr.length
  for (let i = 0; i < len - 1; i ++) {
    for (let j = 0; j < len - 1; j ++) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j + 1]
        arr[j + 1] = arr[j]
        arr[j] = temp
      }
    }
  }
  return arr
}

当然，并不是所有的双重循环都是 O(n²) ，例如：

1
2
3
4
5

for (let i = 0; i < n; i ++) {
  for (let j = 0; j <= 10; j ++) {
    console.log(1)
  }
}

这段代码的实际输出次数应为 10 * n，因此复杂度是 O(n)。

O(logn)

1
2
3
4

let i = 1
while (i < n) {
  i *= 2
}

从以上代码可以看出，在 while 循环中，每次都将 i 乘以2，乘完之后，i 距离 n 就越来越接近了。假设 x 次循环之后，i 就大于 n 了，说明 n = 2^x，求解 x 得，x = log₂n。所以，这段代码的时间复杂度为 O(logn)。

注意：log以几为底并不重要，例如 i = i * 3 或者 i * 10，复杂度也都计为 O(logn)。

O(nlogn)

将时间复杂度为 O(logn) 的代码循环N遍的话，那么它的时间复杂度就是 n * O(logn) ，也就是 O(nlogn) 了。

1
2
3
4
5
6

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

递归算法的时间复杂度

如果递归函数中，递归深度记为 depth，每个递归函数的时间复杂度记为 T，那么总的递归调用的时间复杂度为 O(T * depth)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

function binarySearch (target, arr, start, end) {
  if (end > start) return -1
  start = start || 0
  end = end || arr.length - 1
  
  const mid = (start + end) >> 1
  if (target === arr[mid]) {
    return mid
  } else if (target > arr[mid]) {
    return binarySearch(target, arr, mid + 1, end)
  } else {
    return binarySearch(target, arr, start, mid - 1)
  }
}

在以上的二分查找的代码当中，因为比较中位数的时间复杂度是 O(1)，而每次判断后，要么执行左边的递归，要么执行右边的递归，执行递归的次数为log₂n，所以二分查找的递归时间复杂度为 O(logn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

function quickSort (arr) {
  const len = arr.length
  if (len <= 1) {
    return arr
  }
  const pivotIndex = Math.floor(len / 2)
  const pivot = arr.splice(pivotIndex, 1)[0]
  let left = []
  let right = []
  for (let i = 0; i < len - 1; i ++) {
  	if (arr[i] < pivot) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return quickSort(left).concat([pivot], quickSort(right))
}

还有快排算法，可以看到代码中使用了一次 for 循环，所以执行一次快速排序的时间复杂度是 O(n)，因为每次排序都对数组进行对半排序，所以所需要排序的次数为log₂n + log₂n次（左右两边都要计算），因此快排的时间复杂度为 O(nlogn)。

最好、最坏情况时间复杂度

最好、最坏情况时间复杂度指的是特殊情况下的时间复杂度。

以一个遍历搜索为例：

1
2
3
4
5
6

function find (array, target) {
  for (let i = 0; i < array.length; i++) {
    if (target === array[i]) return i
  }
  return -1
}

当我们查找的元素 target 就是输入数组的第一个元素，则时间复杂度为 O(1)，而当最后一个元素才是 target 时，时间复杂度就是 O(n)。

最好情况时间复杂度就是在最理想情况下执行代码的时间复杂度，它的时间是最短的；最坏情况时间复杂度就是在最糟糕情况下执行代码的时间复杂度，它的时间是最长的。

平均情况时间复杂度

最好、最坏时间复杂度反应的是极端条件下的复杂度，发生的概率不大，不能代表平均水平。那么为了更好的表示平均情况下的算法复杂度，就需要引入平均时间复杂度。

平均情况时间复杂度可用代码在所有可能情况下执行次数的加权平均值表示。

以上面的find函数为例，我们知道，要查找的 target 变量，要么在数组里，要么不在，假设在与不在的概率为 1 /2，而 target 出现在每个位置的概率为 1 / n，那么要查找的 target 出现在每个位置的概率就是 1 / (2n) 。

我们计算这个算法的加权平均值：

最后一个 n / 2 的解释为，target 不在数组中的概率。去掉所有的常数项，则可以得出find算法的平均情况时间复杂度为 O(n)。

均摊复杂度分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14

function insert (array, target) {
  let count = 0
  if (count === array.length) {
    let sum = 0
    for (let i = 0; i < array.length; i++) {
      sum += array[i]
    }
    array[0] = sum
    count = 1
  }
  
  array[count] = val
  count ++
}

这段代码实现了一个往数组中插入数据的功能。当数组满了的时候，我们用 for 循环求和，将求和之后的 sum 值放在第一个位置，再依次插入新值。在最理想的情况下，数组中有空闲空间，最好情况的时间复杂度为 O(1) 。最坏的情况则是数组中没空闲空间，最坏情况的时间复杂度为 O(n)。

如果我们计算段代码的平均情况时间复杂度，则有 n + 1 种情况，前 n 种情况即为数组存在空间，插入第 n 个位置。还有一种情况是数组满了，需要计算 sum 的情况。每种情况的发生概率为 1 / (n + 1)，所以平均情况时间复杂度为：

但其实insert计算平均情况时间复杂度时，并不需要这么复杂，因为在大部分情况下，它的时间复杂度都是 O(1) ，只有极个别的情况下才是 O(n)，所以我们引入了一种更简单的分析方法：均摊复杂度分析。

由于每一次需要 O(n) 的插入操作都会有 n - 1 次耗时 O(1) 的操作，所以每一次操作的平均耗时为：

空间复杂度

一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分：

• 固定部分：这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。
• 可变空间：这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。

空间复杂度可以理解为除了原始序列大小的内存，在算法过程中用到的额外的存储空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

function quickSort (arr) {
  const len = arr.length
  if (len <= 1) {
    return arr
  }
  const pivotIndex = Math.floor(len / 2)
  const pivot = arr.splice(pivotIndex, 1)[0]
  let left = []
  let right = []
  for (let i = 0; i < len - 1; i ++) {
  	if (arr[i] < pivot) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return quickSort(left).concat([pivot], quickSort(right))
}

以这个递归版的快排为例，因为每次递归，都会new两个数组空间来存放新的排序结果，每次排序所需要的新的数组空间为 n - 1，递归深度为log₂n，所以这个快排所耗费的空间复杂度也是 O(nlogn) 。

为了优化空间复杂度，我们可以用指针的形式，直接修改原数组，则空间复杂度会优化为 O(n) ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

function partition (arr, start, end) {
  const pivot = arr[start]
  let left = start
  let right = end
  while (left < right) {
    while (left < right && arr[right] > pivot) {
      right --
    }
    while (left < right && arr[left] <= pivot) {
      left ++
    }
    if (left < right) {
      swap(arr, left, right)
    }
  }
  swap(arr, start, left)
  return left
}

function swap (arr, i, j) {
  const temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

function quickSort (arr, start, end) {
  start = typeof start !== 'number' ? 0 : start
  end = typeof end !== 'number' ? arr.length - 1 : end
  if (start < end) {
  	const partitionIndex = partition(arr, start, end)
    quickSort(arr, start, partitionIndex - 1)
    quickSort(arr, partitionIndex + 1, end)
  }
  return arr
}