时间复杂度

什么是好的算法

判断一个算法的好坏，一般从执行时间和占用空间来看，执行时间越短，占用内存空间越小，那么它就是好的算法。

时间复杂度

时间复杂度的计算并不计算程序具体执行的时间，而是算法执行语句的次数

随着 n 的不算增大，时间复杂度不断增大，算法花费时间越多。常见的时间复杂度有：

• 常数阶 O(1)
• 对数阶 O(log2 n)
• 线性阶 O(n)
• 线性对数阶 O(n log2 n)
• 平方阶 O(n^2)
• 立方阶 O(n^3)
• k次方阶 O(n^k)
• 指数阶 O(2^n)

计算方法

1. 选取相对增长最高的项
2. 最高项系数都化为 1
3. 常数用 O(1) 表示

通常计算时间复杂度都是计算最坏情况，计算时间复杂度的要注意几个点

• 如果算法的执行时间不随 n 的增加而增长，假设算法中有 一千条 语句，执行时间也只是一个较大的常数。此类算法的时间复杂度为：O(1) 。

  let x = 0;
  while (x < 1000) {
    x++;
  }
  

• 有 多个循环语句 的时候，算法的时间复杂度由嵌套层数最多的循环语句中最内层语句的方法决定。例如：在下面for循环中，外层循环每执行一次，内层循环要执行n次，执行次数由 n 决定。时间复杂度是 O(n^2)。

  for(var i=0; i<n; i++) {
    for(var j=0; i<n; j++) {
      //...code
    }
  } 
  

• 循环不仅与 n 有关，还与执行循环判断条件有关。例如以下代码：在代码中，如果 arr[i] 不等于 1 的话，时间复杂度是 O(n)，如果 arr[i] 等于 1 的话，循环不执行，时间复杂度是 O(0)。

  for(var i=0; i<n && arr[i] != 1; i++){
    //...code
  }