時間復雜度的度量方法

130879 閱讀 0 評論 3 點贊

接上文，在理解了時間復雜度的概念后，就可以根據(jù)實際的代碼進行度量了，以下舉例了幾個常用的時間復雜度的表示，對于如何度量其最重要的是觀察程序中的循環(huán)結(jié)構(gòu)，每一個循環(huán)結(jié)構(gòu)代表執(zhí)行循環(huán)中的指令n次，而其余指令一般而言一行代碼代表執(zhí)行一次，對于一個程序而言，執(zhí)行的次數(shù)相差較小其實沒有什么區(qū)別，都是一瞬間執(zhí)行完畢。

1. 度量時間復雜度

a)O(1) / O(C) C代表常數(shù)

#include<stdio.h>
int main(){
    printf("Hello World");  //執(zhí)行一次
    return 0;       //執(zhí)行一次
}

對于如上代碼，執(zhí)行了兩次，即O(2)=O(1)，我們可以稱其時間復雜度為O(1)，或者常數(shù)級時間復雜度

b)O(n)

#include<stdio.h>
int main(){
    int n=10000,ans=0;  //執(zhí)行一次
    for(int i=0;i<n;i++){   //執(zhí)行n次
        ans+=i;     //執(zhí)行一次
    }
    return 0;       //執(zhí)行一次
}

對于如上代碼，我們一共執(zhí)行了n*1+2次，即O(n*1+2)，由上文我們的公式得到其復雜度為O(n)，或稱之為線性階時間復雜度。

c)O(n^2)

#include<stdio.h>
int main(){
    int n=10000,ans=0;  //執(zhí)行一次
    for(int i=0;i<n;i++){   //執(zhí)行n次
        for(int j=0;j<n;j++){   //執(zhí)行n次
            ans+=j;
        }
    }
    return 0;       //執(zhí)行一次
}

對于如上代碼，我們一共執(zhí)行了n*n*1+2次，即O(n*n*1+2)，由上文我們的公式得到其復雜度為O(n^2)，或稱之為平方階時間復雜度，此外還有三層循環(huán)結(jié)構(gòu)嵌套組成的O(n^3)級別的時間復雜度，稱之為立方階時間復雜度，隨著嵌套的增多，甚至還有O(n!)級，稱之為階層級時間復雜度，但是這種級別復雜度極高，程序運行極其緩慢。

d)O(logn)

#include<stdio.h>
int main(){
    int i=1,n=10000;    //執(zhí)行一次
    while(i<=n){    //執(zhí)行l(wèi)ogn次
        i*=2;
    }
    return 0;       //執(zhí)行一次
}

對于如下代碼，與上文的線性增長不同，其i的增長是倍增的形式，也就是說i會隨著運行次數(shù)的增加變大的趨勢變更大，這樣會比那些簡單的用加法上漲的變量更快到達循環(huán)結(jié)構(gòu)的邊界，這樣的代碼時間復雜度一般為log級別，對于本樣例，有O(logn+2)=O(logn)，稱之為對數(shù)階時間復雜度

e)O(n*logn)

#include<stdio.h>
int main(){
    int n=10000,ans=0;  //執(zhí)行一次
    for(int i=0;i<n;i++){   //執(zhí)行n次
        int j=0;        //執(zhí)行1次
        while(j<=n){    //執(zhí)行l(wèi)og(n)次
            j*=2;
        }
    }
    return 0;       //執(zhí)行一次
}

對于上文的對數(shù)級別的時間復雜度，一樣可以實用別的循環(huán)進行嵌套，比如本樣例O(n*(logn+1)+2)=O(n*logn)級別

除此之外還有很多種時間復雜度的組合，比如說O(2^n)這樣的指數(shù)階時間復雜度，有時甚至需要引入多個變量乃進行表示，不過最核心的還是要觀察循環(huán)結(jié)構(gòu)的處理。