分析一個(gè)時(shí)間的復(fù)雜度，推導(dǎo)大O的階
1.用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)
2.在修改后的運(yùn)行次數(shù)的函數(shù)中，只保存最高階項(xiàng)
3.如果最高階項(xiàng)存在且不是1 ，則去除與這個(gè)項(xiàng)相乘的常數(shù)
4.得到的最后結(jié)果就是大O階
判斷這個(gè)的時(shí)間復(fù)雜度
int i = 0 , n = 100;
while(i < n){
i = i *2;
}
由于2^x = n 得到 x = log(2)n ,所以這個(gè)循環(huán)的時(shí)間復(fù)雜度為O(logn).
int i, j ;
for(i = 0; i < n ; i++){
function(1);
}
void function( int count){
printf("%d", count);
}
函數(shù)體打印的這個(gè)參數(shù)偷线，function 函數(shù)的時(shí)間復(fù)雜度是O(1) ,所以整體的時(shí)間復(fù)雜度就是O(n)
void function(int count){
int j ;
for(j =count; j < n ; j++){
printf("%d",j);
}
}
function 的內(nèi)部循環(huán)次數(shù)隨count的增加（接近n）而減少宰睡， 算法的時(shí)間復(fù)雜度為O(n^2)
n++;
function(n);
for(i =0; i < n; i++){
function(i);
}
for(i = 0； i < n ; i++){
for( j = i; j < n; j++){
printf("%d",j);
}
}
void function(int count){
int j ;
for(j =count; j < n ; j++){
printf("%d",j);
}
}
| 例子 | 時(shí)間復(fù)雜度 | 術(shù)語 |
|---|---|---|
| 521314 | O(1) | 常數(shù)階 |
| 3n+4 | O(n) | 線性階 |
| 3n^2+4n+5 | O(n^2) | 平方階 |
| 3log(2)n+4 | O(logn) | 對(duì)數(shù)階 |
| 2n+3log(2)n+14 | O(nlogn) | nlogn階 |
| n3+2n2+4n+6 | O(n^3) | 立方階 |
| 2^2 | O(2^n) | 指數(shù)階 |
常用的時(shí)間復(fù)雜度耗費(fèi)的時(shí)間從小到大是
O(1) < O(logn)<(n) <O(nlogn) < O(n^2) < O(n^3) <O(2^n)<O(n!)<O(n*n)
