时间复杂度和空间复杂度的总结

[JesseZhao1990]

算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。 这也是对比一个算法的优劣的两个指标，时间复杂度和空间复杂度

1.时间复杂度

用来衡量随着输入的值n的增长，运算所用时间的增长情况 首先了解一下执行次数

function f(){
console.log(a);   // 执行一次
var b = 3;        // 执行一次
}

所以以上函数的算法的执行次数是2

时间复杂度的计算方法

将这个函数的执行次数加起来，形成一个表达式。然后丢弃常数，丢弃低幂项，丢弃系数。举几个例子吧

• 例1

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

  当i等于1的时候，执行次数是1，当i是2的时候执行次数也是1，这样依次类推，把整个执行过程的执行次数相加是 T(n) = 1+1+1...+1 因为是n-1个1相加，所以T(n) = n-1 ; 丢失常数，因为没有更低的低次幂和系数，所以，就剩最后一个n。因为这个算法的时间复杂度为O(n);

• 例2

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

当i等于1的时候，执行次数是n-1，当i是2的时候执行次数是n-1. 因此T(n) = (n-1)+ (n-1) + (n-1)+...+(n- 1),因此T(n) = (n-1)*(n-1) = n^2 -2n +1, 丢掉常数低次幂和高次幂的系数。所以时间复杂度为O(n^2)

时间复杂度一般有下面这些 常数阶O(1), 对数阶O(logn), 线性阶O(n), 线性对数阶O(nlogn), 平方阶O(n^2)， 立方阶O(n^3),...， k次方阶O(n^k), 指数阶O(2^n) 。

他们的比较关系为 O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(n^k) < O(2^n)

2.空间复杂度

用来衡量随着输入的值n的增长，运算所占的存储的增长情况