时间复杂度

什么是时间复杂度

在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。时间复杂度常用大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;
}

所以这个算法总共执行了2+2n+5n(n-1)/2次

T(n) = 2+2n+5n(n-1)/2；
忽略掉T(n)中的常量、低次幂和最高次幂的系数，则为f(n)
f(n) = n^2

T(n)/f(n) = (2- 3n + 5/2 n^2 ) / n^2
当n趋向无穷大时，T(n) / f(n)是5/2，为不等于零的常数，则称f(n)是T(n)的同数量级函数。
T(n)=Ｏ(f(n))
所以时间复杂度为O(f(n)) = O（n^2 ）