什么是時(shí)間復(fù)雜度
在計(jì)算機(jī)科學(xué)中买优，算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)末捣，它定量描述了該算法的運(yùn)行時(shí)間。時(shí)間復(fù)雜度常用大O符號(hào)表述篷就，不包括這個(gè)函數(shù)的低階項(xiàng)和首項(xiàng)系數(shù)。
T(n)=O(f(n))
一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱(chēng)為語(yǔ)句頻度或時(shí)間頻度近忙。T(n)表示算法中的語(yǔ)句執(zhí)行次數(shù)竭业，‘；’代表一個(gè)語(yǔ)句結(jié)束及舍。
忽略掉T(n)中的常量未辆、低次冪和最高次冪的系數(shù)，則為f(n)
當(dāng)n趨近于無(wú)窮大時(shí)锯玛，T（n)/f(n)的極限值為不等于零的常數(shù)咐柜，則稱(chēng)f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=Ｏ(f(n)),稱(chēng)Ｏ(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度攘残，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度拙友。
我們常常看到別人描述說(shuō)歼郭，冒泡算法的時(shí)間復(fù)雜度是O(n2)遗契，那么O(n2)是怎么的出來(lái)的呢？
怎么計(jì)算時(shí)間復(fù)雜度
我們就用冒泡排序算法作為例子病曾，來(lái)計(jì)算下時(shí)間復(fù)雜度
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;
}
| 語(yǔ)句 | 執(zhí)行次數(shù) |
|---|---|
| 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 |
所以這個(gè)算法總共執(zhí)行了2+2n+5n(n-1)/2次
T(n) = 2+2n+5n(n-1)/2牍蜂；
忽略掉T(n)中的常量、低次冪和最高次冪的系數(shù)泰涂，則為f(n)
f(n) = n^2
T(n)/f(n) = (2- 3n + 5/2 n^2 ) / n^2
當(dāng)n趨向無(wú)窮大時(shí)鲫竞，T(n) / f(n)是5/2，為不等于零的常數(shù)负敏，則稱(chēng)f(n)是T(n)的同數(shù)量級(jí)函數(shù)贡茅。
T(n)=Ｏ(f(n))
所以時(shí)間復(fù)雜度為O(f(n)) = O（n^2 ）
