复杂度分为两类：时间复杂度和空间复杂度

我们为什么需要复杂度：用来衡量执行一个算法时，数据规模与时间和空间的关系

那什么是复杂度？怎么定义？：

时间复杂度：定性描述算法运行时间的函数

空间复杂度：对一个算法在运行过程中临时占用存储空间大小的量度

请注意，是定性描述。

表示方法： 用 big O 表示法表示，形如 O(n2)

时间复杂度量级：

  • 常数阶 O(1)
  • 对数阶 O(logn)
  • 线性阶 O(n)
  • 线性对数阶 O(nlogn)
  • 平方阶 O(n2)
  • 立方阶 O(n3)
  • k次方阶 O(nk)
  • 阶乘阶 O(n!)
  • 指数阶 O(2n)

对时间复杂度，可以理解为每行代码执行时间都是单位时间，执行次数就是数据量，从而知道执行次数，就能知道复杂度。

比如，下面这段：


i=0
j=0
a=i+j

执行了三次，用 big O 表示法表示为 O(1)，因为 3 是常数，这是常数阶的时间复杂度。

而下面这段


// input n

int sum=0;

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

这里，n 是输入的一个数，代码的执行次数随着 n 的增大而增长，这是一个线性时间 O(n)。

时间复杂度还分：

  • 最好: 代码在最理想情况下执行的时间复杂度
  • 最坏: 代码在最坏情况下执行的时间复杂度
  • 平均: 用代码在所有情况下执行的次数的加权平均值表示
  • 均摊: 在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度

空间复杂度类似，就是算法存储空间与数据量的关系，不赘述