数据结构与算法-01-时间复杂度

算法与数据结构

推导大O阶方法

推导大O阶： 1.用常数1取代运行时间中的所有加法常数 2.在修改后运行次数函数中，只保留最高阶项 3.如果最高阶项存在且不是1，则去除与这个项相乘的常数

(1) 常数阶

时间复杂度为O(1)

1
2
3

int sum=0,n=100;
sum=(1+n)*n/2;
printf("%d",sum);

(2) 线性阶

时间复杂度为O(n),因为循环体要执行n次

1
2
3
4
5

int i;
for(i=0;i<n;i++)
{
    //时间复杂度为O(1)
}

(3) 对数阶

时间复杂度为O(logn)

1
2
3
4
5

int count=1;
while(count<n){
    count=count*2;
    //时间复杂度为O(1)
}

(4) 平方阶

时间复杂度为O(n​^2^)

1
2
3
4
5
6
7

int i,j;
for(i=0;i<n;i++){
    for(j=0;i<n;j++){
        //时间复杂度为O(1)
    }
}
//如果修改为m则时间复杂度为O(m*n)

(5) 常见的时间复杂度

时间复杂度从小到大: O(1)<O(log​n)<O(n)<O(nlogn)<O(n​^2^)<O(n​^3^)<O(2^n^)<O(n!)<O(n​^n^)