概念

表达算法复杂度时候经常会看到O(n) O(1)等,这就是大O表示法,英文(Θ读做theta)

常见复杂度级别

  • Θ(1) 常数级别
  • Θ(log(n)) 对数级别
  • Θ(n) 线性级别
  • Θ(n*log(n)) 线性对数级别
  • Θ(n^2) 平方级别
  • Θ(2^n) 指数级别

简化推导方法

算法执行的操作数去掉所有系数,去掉所有低阶项,只保留最高阶就是最终算法的复杂度。

示例1:

下图的示例代码一共执行了3次,没有低阶项,去掉系数3,则复杂度为Θ(1) O(1)复杂度

示例2:

下图的示例代码一共执行了2n+1次,去掉低阶项1,去掉系数2,则复杂度为Θ(n) O(1)复杂度

示例3:

下图的示例代码一共执行了2n^2+n+1次,去掉低阶项1和n,去掉系数2,则复杂度为Θ(n^2) O(n^2)复杂度

操作数和复杂度对应

操作数 复杂度 名称
100 Θ(1) 常数
100logn+3 Θ(log(n)) 对数
3n+5 Θ(n) 线性
3n+5+100nlogn+3 Θ(n*log(n)) 线性对数
3n+5+ 7n^2 Θ(n^2) 平方
2^n Θ(2^n) 指数

性能

Θ(1)<Θ(log(n))<Θ(n)<Θ(n*log(n))<Θ(n^2)<Θ(2^n)