概念-时间复杂度

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

定义

在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数（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);

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

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

算法的时间复杂度是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;
  }
}

在上面这个双重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);
}

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

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