算法时间复杂度详解与常见示例

什么是时间复杂度

• 是一个函数，用大 O 表示，比如 O(1)、O(n)、O(logN)
• 定性描述该算法的运行时间

示例

O(1)

下面这段代码的执行只会执行一次

let i = 0;
i += 1;

O(n)

for 循环中的代码执行了 n 次

for (var i = 0; i < n; i++) {
  console.log(i);
}

O(n^2)

for 循环中嵌套 for 循环，两个 O(n) 相乘

O(n) * O(n) = O(n^2)

for (var i = 0; i < n; i++) {
  for (var j = 0; j < n; j++) {
    console.log(i, j);
  }
}

O(logN)

如下 i < n 就会在循环内一直执行，相当于一直在执行 2 的 1 次方、2 的 2 次方、2 的 3 次方， 直到 i >= n，也就是 2^(执行次数) >= n，转换为 log 表达式就是 (log(2)(N) = 执行次数: 以 2 为底 N 的对数) 所以这段代码时间复杂度为 O(logN)

let i = 1;
while (i < n) {
  console.log(i);
  i = i * 2;
}

对于 logN 的解释

这应该是高中或者之前数学中的一个表达式，

- log(a)(b) 表示以 a 为底 b 的对数

• 在一些计算器上底默认为 10，因此 log100 = 2 相当于 10 ^ 2 =100
• log(3)(9) = 2 表示以 3 为底 9 的对数, 3 ^ 2 = 9

为什么 O(logN)，没有明确说 logN 的底数是多少

算法中 log 级别的时间复杂度都是由于使用了分治思想,这个底数直接由分治的复杂度决定。如果采用二分法,那么就会以 2 为底数,三分法就会以 3 为底数

相加

取时间复杂度较大的

O(1) + O(n) = O(n)

let i = 0;
i += 1;
for (var i = 0; i < n; i++) {
  console.log(i);
}