什么是时间复杂度

在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。

T(n)=O(f(n))

一个算法中的语句执行次数称为语句频度或时间频度。T(n)表示算法中的语句执行次数，‘；’代表一个语句结束。

忽略掉T(n)中的常量、低次幂和最高次幂的系数，则为f(n)

当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

我们常常看到别人描述说，冒泡算法的时间复杂度是O(n^{2)，那么O(n}2)是怎么的出来的呢？

怎么计算时间复杂度

我们就用冒泡排序算法作为例子，来计算下时间复杂度

function bubbleSort(arr) {    
    var i=arr.length, j;                             
    var tempExchangVal;                           
    while (i > 0) {                              
      for (j = 0; j < i - 1; j++) {          
          if (arr[j] > arr[j + 1]) {                
           tempExchangVal = arr[j]; 
             arr[j] = arr[j + 1]; 
             arr[j + 1] = tempExchangVal; 
         }
        }
        i--;
    }
    return arr;
}

语句	执行次数
var i, j;	1
var tempExchangVal;	1
i > 0	n
j = 0;	n
j < i - 1; j++	n(n-1)/2
arr[j] > arr[j + 1]	n(n-1)/2
tempExchangVal = arr[j];	n(n-1)/2
arr[j] = arr[j + 1];	n(n-1)/2
arr[j + 1] = tempExchangVal;	n(n-1)/2