成人app

復雜度的度量方法

點擊打開在線編譯器,邊學邊練

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

1. 度量時間復雜度

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

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

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

b)O(n)

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

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

c)O(n^2)

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

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

d)O(logn)

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

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

e)O(n*logn)

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

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

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


2.各個復雜度的比較

如圖,我們以x軸為n的規模,y軸為整體的計算次數,可以發現其明顯的計算區別,立方級別似乎很小的數就變得需要很多得計算了,而相對得logn級別得復雜度似乎無論怎么增加n,其漲幅都不是很明顯。

71.png

成人app然而事實上,計算機的計算次數何止60次啊,計算機真實的計算速度是論千論萬論億級別的計算,所以我們的n會變得非常之大,讓我們把坐標進行變化,以10000為界進行理解。

72.png


成人app可以見到,平方以及立方級別的復雜度幾乎已經是平貼著y軸的一條直線了,而O(n*log(n))與O(n)還保持著一定的速率進行增長,log(n)又是另一個極端,它變成了一個幾乎貼著x軸的直線,這樣算法的效率就輕易看得出了。

綜上可以直觀的得出:

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)

成人app在設計程序的時候一定要注意,高計算需求的地方一定不要使用太高的時間復雜度的計算方式!



本文固定URL:http://hnsaiyang.com/course/92

上一課:理解復雜度概念 下一課:內存
第一章 數據結構入門
第二章 鏈表
第三章 棧
第四章 隊列
第五章 從C語言到C++
第六章 串,數組,矩陣,廣義表
第七章 樹
第八章 圖
第九章 算法—查找
第十章 算法—排序
第十一章 算法&競賽,思維培養
第十二章 后記
Dotcpp在線編譯      (登錄可減少運行等待時間)