分析一个时间的复杂度，推导大O的阶
1.用常数1取代运行时间中的所有加法常数
2.在修改后的运行次数的函数中，只保存最高阶项
3.如果最高阶项存在且不是1 ，则去除与这个项相乘的常数
4.得到的最后结果就是大O阶
判断这个的时间复杂度
int i = 0 , n = 100;
while(i < n){
i = i *2;
}
由于2^x = n 得到 x = log(2)n ,所以这个循环的时间复杂度为O(logn).
int i, j ;
for(i = 0; i < n ; i++){
function(1);
}
void function( int count){
printf("%d", count);
}
函数体打印的这个参数，function 函数的时间复杂度是O(1) ,所以整体的时间复杂度就是O(n)
void function(int count){
int j ;
for(j =count; j < n ; j++){
printf("%d",j);
}
}
function 的内部循环次数随count的增加（接近n）而减少， 算法的时间复杂度为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);
}
}
| 例子 | 时间复杂度 | 术语 |
|---|---|---|
| 521314 | O(1) | 常数阶 |
| 3n+4 | O(n) | 线性阶 |
| 3n^2+4n+5 | O(n^2) | 平方阶 |
| 3log(2)n+4 | O(logn) | 对数阶 |
| 2n+3log(2)n+14 | O(nlogn) | nlogn阶 |
| n3+2n2+4n+6 | O(n^3) | 立方阶 |
| 2^2 | O(2^n) | 指数阶 |
常用的时间复杂度耗费的时间从小到大是
O(1) < O(logn)<(n) <O(nlogn) < O(n^2) < O(n^3) <O(2^n)<O(n!)<O(n*n)
