概念-时间复杂度

webkong 6/25/2017 概念时间复杂度

想要深入往往是要从概念开始的。

# 定义

在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数（f(n)）。时间复杂度常用大 O 符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。

例如，如果一个算法对于任何大小为 n （必须比 n₀大）的输入，它至多需要 5n³+ 3n 的时间运行完毕，那么它的渐近时间复杂度是 O(n³)。

时间复杂度是指程序运行从开始到结束所需要的时间。

一个算法中的语句执行次数称为语句频度或时间频度。记为 T(n)。

只是时间复杂度，只有在程序真正执行或者测试的时候才能看到，所以通常的做法就是，从算法中选取一个基础操作或者称为原操作，以基础操作的重复执行次数作为算法的时间度量。

算法的执行次数还要随输入集有关，此时要考虑所有可能输入数据的期望值，此时的算法时间复杂度叫平均时间复杂度。

算法的基本操作重复执行的次数是模块 n 的某一个函数 f(n)，因此，算法的时间复杂度记做：T(n)=O(n）。随着模块 n 的增大，算法执行的时间的增长率和 f(n)的增长率成正比，所以 f(n)越小，算法的时间复杂度越低，算法的效率越高。

大多数情况下，基础操作是最深层循环内的语句中的操作。

按数量级递增排列，常见的时间复杂度有：常数阶 O(1), 对数阶 O(log₂n), 线性阶 O(n), 线性对数阶 O(nlog₂n), 平方阶 O(n²)，立方阶 O(n³),...， k 次方阶 O(n^k), 指数阶 O(2ⁿ) 。

let a = 0,
  n = 100;

a = ((1 + n) * n) / 2;

console.log(a);

1
2
3
4
5
6

算法的时间复杂度为 O(1)。这个算法的运行次数函数是 f(n) = 1+1+1 = 3, 把常数项改为 1，所以时间复杂度是 O(1)。

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

1
2
3
4

算法的时间复杂度是 O(n)。这个的算法的运行次数函数 f(n) = n+n = 2n , 把常数改为 1，所以时间复杂度是 O(n)。

let x = 0;
for (let i = 0; i < n; i++) {
  for (let j = 1; j <= i; j++) {
    ++x;
  }
}

1
2
3
4
5
6

在上面这个双重 for 循环中，基础操作++x执行了1+2+3+ ... +n-1次，即 n*(n-1)/2 = （n²-2n）/2，所以时间复杂度是 O(n²)；

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

1
2
3
4
5
6

算法的时间复杂度是 O(log₂n)。当每次i乘以 2 之后，i的值渐进于 n，也就是说，有多少个 2 相乘之后会大于 n,就会退出循环。 2^x = n, x 就是运行的次数， x = log₂n 。

更多的时间复杂度列表参见维基百科-时间复杂度^[2]。