时间复杂度

算法的效率

虽然计算机能快速的完成运算处理，但实际上，它也需要根据输入数据的大小和算法效率来消耗一定的处理器资源。要想编写出能高效运行的程序，我们就需要考虑到算法的效率。算法的效率主要由以下两个复杂度来评估：时间复杂度：评估执行程序所需的时间。可以估算出程序对处理器的使用程度。空间复杂度：评估执行程序所需的存储空间。可以估算出程序对计算机内存的使用程度。
设计算法时，一般是要先考虑系统环境，然后权衡时间复杂度和空间复杂度，选取一个平衡点。不过，时间复杂度要比空间复杂度更容易产生问题，因此算法研究的主要也是时间复杂度，不特别说明的情况下，复杂度就是指时间复杂度。

时间复杂度

同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行时，效率均不同。所以，精确度量算法的执行时间没有太大意义。 一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律，为此我们引入时间复杂度的概念。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数，记作T(n)=O(f(n))，它称为算法的渐进时间复杂度，简称时间复杂度。

计算规则（大o表示法）

1.用常数1来取代运行时间中所有加法常数。
2.修改后的运行次数函数中，只保留最高阶项
3.如果最高阶项存在且不是1，则去除与这个项相乘的常数。

例子

  var num = 0;
  num += 10
  console.log(num)

  语句频度：f(n) = f(1) = 3
  时间复杂度：T(n) = O(f(n)) = O(3) = O(1)
  O(1)称为常数阶

  var num = 0,i,n;     //执行1次
  for (i = 0;i < n;i++){   // n次
      num++              //n次
  }
  console.log(num)  //1次

  语句频度：f(n) = 1+n+n+1
  时间复杂度：T(n) = O(f(n)) = O(2n+2) = O(n)
  O(n)称为线性阶

  var num = 0,i,j,n,m;     //执行1次
  for (i = 0;i < n;i++){   // n次
    for (j = 0;j < m;i++){   // n*m次
      num++              //n*m次
  }
    console.log(num)  //n次
  }

  语句频度：f(n) = 2mn+2n+1
  如果 m=n, f(n) = 2n²+2n+1
  时间复杂度：T(n) = O(f(n)) = O(2n²+2n+1) = O(n²)
  O(n)称为平方阶

再来一个相对较复杂的算法（以冒泡排序为例,依次递增）

  function BubbleSort(arr) {
      var i,j,temp,n = arr.length; // 1
      for(i = 1; i<n; i++) {         //n-1次
          for(j = 0; j<n-i; j++) {   //n-1+n-2+n-3 +...+1,n(n-1)/2次
            if(arr[j] > arr[j+1]) {  //n(n-1)/2次
                temp = arr[j]        //0或n(n-1)/2次
                arr[j] = arr[j+1]    //0或n(n-1)/2次
                arr[j+1] = temp;     //0或n(n-1)/2次
            }
       }
      }
  }
  最好情况下(数据不发生交换) f(n) = n²
  最坏情况下(数据都发生交换) f(n) = 5/2n²-3/2n
  T(n)最好 = T(n)最坏 = O(n²)

除了常数阶、线性阶、平方阶，还有如下时间复杂度：f(n)=nlogn时，时间复杂度为O(nlogn)，可以称为nlogn阶。f(n)=n³时，时间复杂度为O(n³)，可以称为立方阶。f(n)=2ⁿ时，时间复杂度为O(2ⁿ)，可以称为指数阶。f(n)=n!时，时间复杂度为O(n!)，可以称为阶乘阶。f(n)=(√n时，时间复杂度为O(√n)，可以称为平方根阶。
复杂度直观图：

time.jpg