复杂度分析 - Hero · 算法 · Hello 算法

时间复杂度

推算方法

第一步：统计操作数量

function algorithm(n) {
  let a = 1; // +0（技巧 1）
  a = a + n; // +0（技巧 1）
  // +n（技巧 2）
  for (let i = 0; i < 5 * n + 1; i++) {
    console.log(0);
  }
  // +n*n（技巧 3）
  for (let i = 0; i < 2 * n; i++) {
    for (let j = 0; j < n + 1; j++) {
      console.log(0);
    }
  }
}

// 精细统计
T(n) = 2n * (n + 1) + (5 * n + 1) + 2
     = 2n² + 7n + 3

// 粗略统计
T(n) = n² + n

第二步：判断渐近上界

时间复杂度由T(n)中最高阶的项来决定

示例：

操作数量(T(n))	时间复杂度O(f(n))
1000	O(1)
3n + 2	O(n)
n² + 2n + 2	O(n²)
n3 + 2	O(n3)

常见类型

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(2ⁿ) < O(n!)

常数阶< 对数阶 < 线性阶 < 线性对数阶 < 平方阶 < 指数阶 < 阶乘阶

最差、最佳、平均时间复杂度

“最差时间复杂度”对应函数渐近上界，使用大记号O表示。相应地，“最佳时间复杂度”对应函数渐近下界，用记号Ω表示

空间复杂度

一般只考虑 暂存数据、栈帧空间和输出数据三部分

推算方法

1. 以最差输入数据为准
2. 以算法运行中的峰值内存为准

常见类型

O(1) < O(logn) < O(n) < O(n²) < O(2ⁿ)

常数阶 < 对数阶 < 线性阶 < 平方阶 < 指数阶