什麼是演算法時間複雜度?

語言: CN / TW / HK

本文已參與 「掘力星計劃」 ,贏取創作大禮包,挑戰創作激勵金。

一、時間複雜度的定義

在進行演算法分析時,語句總的執行次數T(n)是關於問題規模n的函式,進而分析T(n)隨n的變化情況並確定T(n)的數量級。

演算法的時間複雜度,也就是演算法的時間量度,記作:T(n)=O(f(n))。它表示隨問題規模n的增大,演算法執行時間的增長率和f(n)的增長率相同,稱作演算法的漸近時間複雜度,簡稱為時間複雜度。其中f(n)是問題規模n的某個函式。這樣用大寫O( )來體現演算法時間複雜度的記法,我們稱之為大O記法。

一般情況下,隨著n的增大,T(n)增長最慢的演算法為最優演算法。

顯然,由此演算法時間複雜度的定義可知,我們分別給常見的時間複雜度取了非官方的名稱,O(1)叫常數階O(n)叫線性階O(n²)叫平方階O(logn)對數階,當然,還有其他的一些階,我們之後會介紹。

二、大O階推導

我們可以通過下面的方法推匯出演算法的時間複雜度,稱之為推導大O階

1)用常數1取代執行時間中的所有加法常數。
2)在修改後的執行次數函式中,只保留最高階。
3)如果最高階項存在且不是1,則去除與這個項相乘的常數。

以上得到的結果就是大O階

2.1 常數階

int sum = 0,n = 100; /* 執行一次 */ sum = (1 + n) * n / 2; /* 執行一次 */ printf("%d", sum); /* 執行一次 */ 假設有如上的一個演算法,沒學過演算法的同學可能會認為該演算法的時間複雜度是O(3),但實際上是O(1)。根據我們的上面的大O階推導,第一步,用1取代3,就成了1,第二步,該演算法根本沒有最高階,所以演算法時間複雜度就是O(1)。

假設有如下的演算法,其中有十句 sum = (1 + n) * n / 2; / 執行一次 / int sum = 0,n = 100; /* 執行一次 */ sum = (1 + n) * n / 2; /* 執行一次 */ sum = (1 + n) * n / 2; /* 執行一次 */ sum = (1 + n) * n / 2; /* 執行一次 */ sum = (1 + n) * n / 2; /* 執行一次 */ sum = (1 + n) * n / 2; /* 執行一次 */ sum = (1 + n) * n / 2; /* 執行一次 */ sum = (1 + n) * n / 2; /* 執行一次 */ sum = (1 + n) * n / 2; /* 執行一次 */ sum = (1 + n) * n / 2; /* 執行一次 */ sum = (1 + n) * n / 2; /* 執行一次 */ printf("%d", sum); /* 執行一次 */ 在上面的演算法中,程式碼執行了12行,實際與最初的3行沒有差別,因為與問題的本質:n的大小無關,所以最終該演算法的時間複雜度仍然是O(1)。

關於上面的兩種我們稱之為具有O(1)的時間複雜度,又稱為常數階

2.2 線性階

int i; for (i = 0; i < n; i++) { /* 時間複雜度為O(1)的程式步驟序列 */ } 如上面的程式碼所示,在迴圈內部的程式碼,其複雜度是O(1),重點在於n的大小,它決定迴圈的次數,則整個演算法的時間複雜度是O(n)。

2.3 對數階

int count = 1; while (count < n) { count = count * 2; /* 時間複雜度為O(1)的程式步驟序列 */ } 如上程式碼所示,count的增長速度是每次乘以2,假設count = 10 ,n=100,則有以下等式: 10 * 2 = 20 20 * 2 = 40 40 * 2 = 80 最終就是10 * 2的三次方 = 80。所以我們得到結論 count * 2的x次方 = n,根據大O階推導,將count用常數1替換,則x = log2n。所以這個迴圈的時間複雜度是O(logn)。

2.4 平方階

int i, j; for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { /* 時間複雜度為O(1)的程式步驟序列 */ } } 有如上的巢狀迴圈,其記憶體迴圈是一個線性階,則其時間複雜度是O(n),外部迴圈的時間複雜度同樣是O(n),相當於記憶體的O(n)迴圈了n次,則此程式碼的時間複雜度就是O(n²)。

如果有如下的演算法: int i, j; for (i = 0; i < m; i++) { for (j = 0; j < n; j++) { /* 時間複雜度為O(1)的程式步驟序列 */ } } 上面的時間複雜度就是O(mn)。

下面看一種複雜的情況如何推導其時間複雜度: int i, j; for (i = 0; i < n; i++) { /* 注意j = i 而不是0 */ for (j = i; j < n; j++) { /* 時間複雜度為O(1)的程式步驟序列 */ } } 當i = 0 時,內部執行了n次;當i = 1時,內部執行了n-1,以此類推: n + (n-1) + (n-2) + .... .... + 1 對以上公式進行轉化,首項加尾項是n+1,總共有n個n+1,則等到以下公式: (n(n+1))/2 = n²/2 + n/2 下面根據大O階推導:
1)沒有加法常數,所以不替換
2)保留最高項,即n²/2
3)去除常數,就是去掉1/2,則等到最終的結果是n²。

如上可以得到一些結論,其實其推導過程不難,難在如何將數列進行轉化,如上的等差數列等。

2.5 其他的時間複雜度

除了前面介紹的之外,還有一些其他的時間複雜度。

立方階:O(n³) 指數階:2ⁿ n成對數階:nlogn 階乘階:n! n的n次方:nⁿ

這些所有的時間複雜度耗時大小如下所示: O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

三、演算法空間複雜度

空間換時間的方式。

演算法空間複雜度的計算公式記作:S(n)=O(f(n)),其中,n為問題的規模,f(n)為語句關於n所佔儲存空間的函式。

我們都使用“時間複雜度”來指執行時間的需求,使用“空間複雜度”指空間需求。當不用限定詞地使用“複雜度”時,通常都是指時間複雜度。

本文重點是時間複雜度,關於空間複雜度就不多做介紹了。