定義
在計(jì)算機(jī)科學(xué)中，算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)稻薇，它定量描述了該算法的運(yùn)行時(shí)間嫂冻。這是一個(gè)代表算法輸入值的字符串的長度的函數(shù)。時(shí)間復(fù)雜度常用大O符號(hào)表述塞椎，不包括這個(gè)函數(shù)的低階項(xiàng)和首項(xiàng)系數(shù)桨仿。使用這種方式時(shí)，時(shí)間復(fù)雜度可被稱為是漸近的案狠，亦即考察輸入值大小趨近無窮時(shí)的情況服傍。
常數(shù)階
int sum = 0,n = 100;
sum = (1 + n)*n/100;
時(shí)間復(fù)雜度為O(1)。
線性階
sum = 0;
for(int i = 1; i <= n; i ++){
sum += i;
}
循環(huán)體中的代碼必須執(zhí)行n次骂铁，循環(huán)的時(shí)間復(fù)雜度為O(n)吹零。
對(duì)數(shù)階
int count = 1
while(count < n){
count = count * 2;
}
x個(gè)2相乘大于n后，就會(huì)推出循環(huán)拉庵。由2^x=n灿椅，得到x = log2n。
所以這個(gè)循環(huán)體的時(shí)間復(fù)雜度為O(logn)钞支。
平方階
for(int i = 0; i < n; i ++){
for(int j = 0; j< n; j++){
//時(shí)間復(fù)雜度為O(1)的語句
}
}
時(shí)間復(fù)雜度為O(n*n), 即O(n^2)茫蛹。
常見的時(shí)間復(fù)雜度
| 執(zhí)行次數(shù)函數(shù) | 階 |
|---|---|
| 12 | O(1) |
| n+9 | O(n) |
| 2n^2+3n+9 | O(n^2) |
| 3log2n+8 | O(logn) |
| 4n+3nlog2n+8 | O(nlogn) |
| 7n^3 + 3n^2 + 6n+5 | O(n^3) |
| 2^n | O(2^n) |
