【数据结构】时间复杂度的计算方法

飞熊 • 2024年2月4日下午10:10 • 技术随笔 • 阅读 286

时间复杂度的计算方法

我们通常把程序执行的次数叫做频度。
频度函数 f(n) 计算程序的频度之和

时间复杂度： T（n） = O（ f（n））
大O表示法的几种常见情况：

复杂度为常数，如23，9999，等等都表示为O(1)
复杂度包含n时，省略系数与常数项，只取n的最高阶项如：2n+45 为 O(n) ； 4n³⁺⁶ⁿ2+n 为O(n^3)
复杂度为对数时：如log5(n)、log2(n) 等等都表示为 O(logn)
省略低阶，只取高阶 (即取最大的),类似与高数极限的抓大头如：logn+nlogn 表示为O(nlogn)

复杂度大小：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

实例

例一：

void method1(){
    printf("祝你"); //执行1次
    printf("诸事顺利"); //执行1次
    printf("万事如意"); //执行1次
}
// f(n) = 1+1+1 = 3

结果：

f（n）= 1 + 1 + 1 = 3
T（n）= O（ f（n）） = O（3） = O （1）

例二：

void method2(){
    for(int i=0;i<5;i++){ //i=0 执行1次；i<5 判断5+1次,等于5时判断后退出；i++ 执行5次
        printf("!"); //执行5次
    }
}  //1+(5+1)+5+5 = 17

结果：

f（n）= 1+(5+1)+5+5 = 17
T（n）= O（ f（n）） = O（17） = O （1）

例三：

void method3(int n){
    for(int i=0;i<n;i++){ //i=0 执行1次；i<n 执行n+1次；i++ 执行n次
        printf("!"); //执行n次，你会有n次好运哦
    }
} //1+(n+1)+n+n = 3n+2

结果：

f（n）= 1+(n+1)+n+n = 3n+2
T（n）= O（ f（n）） = O（3n+2） = O （n）

例四：

void method4(int n){
    for(int i=0;i<n;i++){  //i=0 执行1次；i<n 执行n+1次；i++ 执行n次
        //整个内层循环 执行n次
        for(int j=0;j<n;j++){ //j=0 执行1次；j<n 执行n+1次；j++ 执行n次
            printf("!"); //执行n次
        }
}} //外层2n+2; 复杂度：2n+2+n*(3n+2) = 3n^2+4n+2