前置知识：选择排序、冒泡排序、插入排序、等差数列、等比数列

建议：不要跳过

常数操作

常数操作：固定时间的操作，执行时间和数据量无关

如：加减乘除等运算、位运算、数组索引、hash 函数

不管是 3 + 5 还是 3千万 + 20亿，它们所需的时间是一样的，都是常数操作。为什么？因为整数是固定 32 位，都是进行 32 位各位相加

不管是取数组的第 1 项还是取它的第 5 亿项，它们所需的时间是一样的，都是常数操作。为什么？因为数组空间是连续的，依据数组元素所占空间的大小和第几项即可求出所取元素内存地址相对数组首元素内存地址（即：数组地址）的偏移量，直接去读那块空间即可

常数时间的操作也有快慢之分，如 hash 函数是由多个常数操作拼起来的，它肯定要比加减乘除运算慢；再如加减乘除等运算是由位运算拼出来的，肯定要比位运算慢；内存寻址要比算术运算慢……

而一些操作不是常数操作，如：遍历数组取最大值、链表索引

遍历数组明显是和数据量有关的，而链表索引，由于链表数组空间非连续，要从上一个元素的指针才能找到下一个元素，所以要从第一项遍历链表才能找到第 n 项

时间复杂度和空间复杂度

时间复杂度：算法的操作单元（常数操作）数量和数据量 n 的关系。它定性描述该算法的运行时间
空间复杂度：算法的额外空间占用和数据量 n 的关系

什么是额外空间？不算输入输出数据的空间，而是完成算法所需的辅助空间

复杂度的意义

当数据量 n 从 $0 \to \infty$ 时，算法的运行时间、额外空间占用的变化趋势，即：复杂度与数据量的关系，当数据量很大时，谁起决定性作用

这也正是为什么可以忽略低次项、常数项和最高次项系数的原因，因为当数据量 $n \to \infty$ 时，这些东西都太微不足道了

复杂度是考虑最差情况

拿之前写过的“三傻排序”估计其时间复杂度，选择排序和冒泡排序没什么好说的，都是等差数列，时间复杂度是 n^2（舍去低次项、常数项和最高次项系数）

插入排序，当数组已经是有序的了（最好情况），它在每一项只向前看一眼就知道不小于前一项，继续下一项了，所以时间复杂度是 n；而当数组是逆序的（最差情况），则每一项都要向前交换到第一项，所以时间复杂度是 n^2

如何判断复杂度？考虑最差情况！即：大 O 表示法，记作：O(n^2)，意为 n^2 的复杂度是该算法的渐进上界（最差情况是 n^2，不会比 n^2 更差）

同理，还有：

$Θ$ 表示法：平均情况
$Ω$ 表示法：最好情况，渐进上界（最好情况，不会更好）

其实上面所说的考虑最差情况要是严格固定流程的算法，与之对应的：算法中的随机行为，要以其平均或概率期望估算复杂度

如：设计一个算法生成一个相邻元素不同的数组

思路：遍历数组每一项，生成一个随机数，比较它和前一项是否相同，相同则重新生成一个

估算时间复杂度，最差情况： $O (\infty)$ ！因为生成的随机数可能一直和前一项相同

但这是没有意义的，且不符合事实，期望来看，它的复杂度就是遍历一遍数组就完事了，即：O(n)

算法流程上利用随机行为作为重要部分的的算法有很多，如：随机快速排序、跳表等

事前估计和事后分析

其实判断算法的优劣不一定要用复杂度来看，还可以直接跑代码，测试所需时间和占用空间，这就是事后分析的方法；而之前所说的估算复杂度则完全不用跑代码，只分析代码的流程就可以，是事前估计的方法

一般使用时空复杂度判断算法优劣，即：事前估计法

如果两个算法的复杂度相同，要如何比较优劣呢？一是可以看系数、低次项、常数项等；二是可以放弃理论分析、选择用实验来确定（事后分析）

复杂度的均摊

以动态数组的扩容为例，当添加某一项时，数组容量不够，则扩容为原来的一倍，再将原数组内容复制到新数组中，它的时间复杂度是 O(n)，所以动态数组动态数组添加元素的时间复杂度是 O(n) 吗？

不是的，因为只有容量不够时才进行扩容，一次就会扩 1 倍或 0.5 倍（go 中），为了方便估算其复杂度，可以将扩容的代价分摊到每一次添加元素时，则每次添加元素的扩容代价为 O(1)，所以动态数组动态数组添加元素的时间复杂度是 O(1)

并查集、单调队列、单调栈、哈希表等结构，都有均摊的这个概念。这些内容【必备】课都会讲

最优解

先满足时间复杂度最优，然后尽量少用空间的解

在现在来看，由于硬件的发展，节省空间的重要程度要远远低于执行效率；但对于看重空间的情况（如：嵌入式）要提高空间占用的重要程度

判断复杂度的错误方法

注意：不要用代码结构来判断复杂度

比如：我看见 “三傻排序” 都是循环套循环，所以它们都是 O(n^2) 的时间复杂度

那修改一下冒泡排序的写法，它只有一个循环，难道它的时间复杂度是 O(n) 吗？

// 冒泡排序
func bubbleSort(arr []int) {
  n := len(arr)
  i := n - 1
  j := 0
  for i > 0 {
    if arr[j] > arr[j+1] {
      arr[j], arr[j+1] = arr[j+1], arr[j]
    }
    if j < i-1 {
      j++
    } else {
      i--
      j = 0
    }
  }
}

不是的，它和之前写的冒泡排序思路是一模一样的，只是变化了一下写法，它的时间复杂度仍然是 O(n^2)

再举个例子：

n := 200000
for i := 1; i <= n; i++ {
  for j := i; j <= n; j+=i {
    // do something
  }
}

它的时间复杂度是 O(n^2) 吗？不是的！它的时间复杂度是 $n + \frac{n}{2} + \frac{n}{3} + \dots + \frac{n}{n}$ ，提出 $n$ 变成 $(1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}) \times n$ ，其中 $1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}$ 是调和级数，其值收敛于 logn，所以原算法的时间复杂度是 O(nlogn)

package main
 
import (
  "fmt"
  "time"
)
 
func main() {
  n := 200000
 
  start := time.Now()
  // 调和级数：O(nlogn)
  for i := 1; i <= n; i++ {
    for j := i; j <= n; j += i {
      // do something
    }
  }
  elapsed := time.Since(start)
  fmt.Println("调和级数耗时：", elapsed) // 835.883µs
 
  start = time.Now()
  // 等差数列：O(n^2)
  for i := 1; i <= n; i++ {
    for j := i; j <= n; j++ {
      // do something
    }
  }
  elapsed = time.Since(start)
  fmt.Println("等差数列耗时：", elapsed) // 5.250815235s
}

所以，不要用代码结构来判断复杂度，而是要分析算法的逻辑。时间复杂度只能是对算法流程充分理解才能分析出来，而不是简单的看代码结构

常见复杂度一览

常数阶： $O (1)$
对数阶： $O (l o g^{n})$
线性阶： $O (n)$
线性对数阶： $O (n \times l o g^{n})$
次方阶： $O (n^{2}) 、 \dots 、 O (n^{k})$
指数阶： $O (2^{n}) 、 \dots 、 O (k^{n})$
阶乘阶： $O (n!)$

根据数据量猜解法

时间复杂度非常重要，可以直接判断某个方法能不能通过一个题目，根据数据量猜解法，【必备】课都会讲

整套课会讲很多算法和数据结构，也会见到很多的时间复杂度的表达，持续看课即可

等差数列

等差数列：从第二项起，每一项与它的前一项的差等于同一个常数的一种数列，常用 A、P 表示。这个常数叫做等差数列的公差，公差常用 d 表示

通项公式为： $a_{n} = a_{1} + (n - 1) \times d$

求和公式

若一个等差数列的首项为 $a_{1}$ ，末项为 $a_{n}$ ，那么该等差数列和表达式为 $S = \frac{n ( a _{1} + a _{n} )}{2}$

前 n 项和公式： $S_{n} = n \times a_{1} + \frac{n \times ( n - 1 )}{2} \times d$

其中， $S_{n}$ 是等差数列前 n 项的和； $n$ 是项数； $a_{1}$ 是首项； $d$ 是公差

化简得： $S = a n^{2} + bn + c$ ，其中 $a$ 、 $b$ 、 $c$ 都是常数

My-Notes

全部文章

007.时间复杂度和空间复杂度