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

小咪咪 2023-09-23 19:12 114阅读 0赞

### 时间复杂度的计算方法 ###

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

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

1.  复杂度为常数，如23，9999，等等 都表示为O(1)
2.  复杂度包含n时，省略系数与常数项，只取n的最高阶项 如：2n+45 为 O(n) ； 4n3+6n2+n 为O(n^3)
3.  复杂度为对数时：如log5(n)、log2(n) 等等 都表示为 O(logn)
4.  省略低阶，只取高阶 (即取最大的),类似与高数极限的抓大头 如：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

结果：

> f（n）= 2n+2+n\*(3n+2) = 3n^2+4n+2  
> T（n）= O（ f（n）） = O（3n^2+4n+2） = O （n^2）