什么是时间复杂度
在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。时间复杂度常用大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(n2)，那么O(n2)是怎么的出来的呢？
怎么计算时间复杂度
我们就用冒泡排序算法作为例子，来计算下时间复杂度
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 |
所以这个算法总共执行了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 ）
