跳到主要内容

复杂度分析✅

什么是大 O 表示法，它的作用是什么？​

答案

复杂度分析用于评估算法的优劣。 复杂度分析分为两个方面

  • 时间复杂度 评估算法执行效率
  • 空间复杂度 评估算法资源占用

由于代码的执行效率多和输入数据规模相关。采用大 O 表示法评估时间或空间复杂度随数据规模的增长趋势。

由于目前计算机硬件能力提升,主要关心时间复杂度。典型的时间复杂度的大 O 表示如下:

  • O(1) 常量型操作,不随数据量增大发生变化效率最高
  • O(logn) 对数增长
  • O(n) 线性增长
  • O(nlogn)
  • O(n^2)
  • O(n!) 阶乘增长

空间复杂度同理

利用如下规则简化复杂度分析

  1. 忽略常数项 O(2n) => O(n)
  2. 相加取复杂度大的 O(n) + O(n^2) => O(n^2)
  3. 相乘则复杂度也相乘 O(n)*O(n) => O(n^2)

复杂度分类

  • 最好
  • 最坏
  • 平均

高级复杂度分析

  • 摊还分析：用于分析具有摊还成本的算法，如动态数组的扩展。
  • 递归树方法：用于分析递归算法的复杂度。

示例

// O(1) 常量时间复杂度
function constantTimeOperation (arr) {
  return arr[0]
}

// O(n) 线性时间复杂度
function linearTimeOperation (arr) {
  for (let i = 0; i < arr.length; i++) {
    console.log(arr[i])
  }
}

// O(n^2) 平方时间复杂度
function quadraticTimeOperation (arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      console.log(arr[i], arr[j])
    }
  }
}
22%