复杂度分为两类:时间复杂度空间复杂度

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

那什么是复杂度?怎么定义?:

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

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

请注意,是定性描述。

表示方法: 用 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)。

时间复杂度还分:

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

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