算法是用于解決特定問題的一系列的執行步驟。使用不同算法，解決同一個問題，效率可能相差非常大。為了對算法的好壞進行評價，我們引入?“算法復雜度”?的概念。

?

1、引例：斐波那契數列（Fibonacci sequence）

已知斐波那契數列：，求它的通項公式。

求解斐波那契數列的方法有很多種，這里只介紹兩種：遞歸法和平推法。

package com.atangbiji;public class Main {public static void main(String[] args) {// 輸出通項F(n)System.out.println(fib1(1));System.out.println(fib1(2));System.out.println(fib1(3));System.out.println(fib1(4));System.out.println(fib1(5));System.out.println(fib2(70));}/** 求斐波那契數列（Fibonacci sequence）* F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）的通項F(n).*//** 方法一：遞歸法* 最高支持 n = 92 ，否則超出 Long.MAX_VALUE* @param n * @return f(n) * */public static long fib1(int n) {if (n < 1 || n > 92)return 0;if (n < 3)return 1;return fib1(n - 1) + fib1(n - 2);}/** 方法二：平推法* 最高支持 n = 92 ，否則超出 Long.MAX_VALUE* @param n * @return f(n) * */public static long fib2(int n) {if (n < 1 || n > 92)return 0;//n: 1 2 3 4 5 ……//F(n): 1 1 2 3 5 ……long first = 1;long second = 1;for (int i = 3; i <= n; i++) {long sum = first + second;first = second;second = sum;}return second;}}

通過測試，我們可以發現：當n的取值較大時（如：n = 60），若采用遞推法計算則會發現遲遲不出結果，若采用平推法計算則可以秒出結果。由此可見，?平推法的效率明顯高于遞推法。

?

2、如何評估算法的好壞？

• 正確性

• 可讀性

• 健壯性：對不合理輸入的反應能力和處理能力。

• 時間復雜度（time complexity）：?估算程序指令的執行次數（執行時間）。

• 空間復雜度（space complexity）：?估算所需占用的存儲空間。

注：一般情況下，我們主要考慮算法的時間復雜度。?（因為目前計算機的內存一般都比較大）

?

3、時間復雜度的估算

我們可以用程序指令的執行次數來估算時間復雜度。例如：

（1）函數test1

public static void test1(int n) {//總執行次數 = 14// 1（判斷語句可以忽略）if (n > 10) {System.out.println("n > 10");} else if (n > 5) {System.out.println("n > 5");} else {System.out.println("n <= 5");} // 1 + 4 + 4 + 4 for (int i = 0; i < 4; i++) {System.out.println("test"); }}

（2）函數test2

public?static?void?test2(int?n)?{//總執行次數 = 1 + 3n//1 + n + n + nfor (int i = 0; i < n; i++) {System.out.println("test");} }

（3）函數test3

public static void test3(int n) {//總執行次數 = 48n + 1// 1 + 2n + n * (1 + 45)for (int i = 0; i < n; i++) {for (int j = 0; j < 15; j++) {// 1 + 15 + 15 + 15System.out.println("test");} }}

（4）函數test4

public?static?void?test4(int?n)?{//總執行次數 = 3n^2 +3n +1// 1 + 2n + n * (1 + 3n)for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) { // 1 + n + n + nSystem.out.println("test");}} }

（5）★ 函數test5

public static void test5(int n) {//總執行次數 = log2(n)/** n = 2 , 執行 1 次* n = 4 , 執行 2 次* n = 8 , 執行 3 次 * */while ((n = n/2) > 0) { // 倍速減小System.out.println("test"); // 只考慮這一句的執行次數} }

（6）函數test6

public?static?void?test6(int?n)?{//總執行次數 = log5(n)while ((n = n/5) > 0) {System.out.println("test"); // 只考慮這一句的執行次數} }

（7）函數test7

public?static?void?test7(int?n)?{//總執行次數 = 3n*log2(n) + 3log2(n) + 1// 1 + 2 * log2(n) + log2(n) * (1 + 3n)/** n = 2 , 執行 1 次* n = 4 , 執行 2 次* n = 8 , 執行 3 次 * */for (int i = 1; i < n; i += i) { // i = i + i = i * 2（倍速增大）for (int j = 0; j < n; j++) { // 1 + n + n + nSystem.out.println("test");}} }

?

4、大O表示法

為了進一步簡化復雜度的計算，我們一般使用大O表示法來描述時間（或空間）復雜度。它表示的是?數據規模為n?時算法所對應的復雜度。

大O表示法的性質：

（1）可以忽略常數、常系數和低階項。

• 9 >> O（1）

• 2n + 3 >> O（n）

• 3n^2?+ 2n + 6 >> O（n^2）

（2）對數階一般省略底數，統稱 log n。

• log2 n = log2 9 * log9 n

注：大O表示法僅僅只是一種粗略的分析模型，是一種估算。?它能幫我們快速了解一個算法的執行效率。

?

5、常見的復雜度

其中：

• 當數據規模較小時，?各復雜度對應的曲線如下圖所示。

  ?

• 當數據規模較大時，?各復雜度對應的曲線如下圖所示。

所以，當數據規模比較大時，復雜度為??我們就很難接受了。

?

6、斐波那契數算法復雜度分析

（1）遞歸法

public?static?long?fib1(int?n)?{if (n < 1 || n > 92) return 0; if (n < 3) return 1; return fib1(n - 1) + fib1(n - 2);}

假設計算時和的值已經得到，我們可以發現該函數每次執行的時間主要取決于求和運算。因此，該算法函數指令的執行次數等價于該函數被遞歸調用次數。

當時，該函數的調用過程如下圖所示。

所以，該函數被遞歸調用的次數??二叉樹的節點數。

即：。

因此，該算法的復雜度為。

注：?細心的同學可能會發現，當時，函數被遞歸調用的次數并不完全等于。

這里需要說明的是：復雜度是一種估算，我們關心的不是具體的數值，而是量級和趨勢。?所以，呈指數級增長的趨勢是毋庸置疑的。

（2）平推法

public static long fib2(int n) {if (n < 1 || n > 92)return 0;//n: 1 2 3 4 5 ……//F(n): 1 1 2 3 5 ……long first = 1;long second = 1;for (int i = 3; i <= n; i++) {long sum = first + second;first = second;second = sum;}return second; }

顯然，平推法的時間復雜度為。

?

7、算法的優化方向

（1）用盡量少的執行步驟（運行時間）。

（2）用盡量少的存儲空間。

（3）根據情況，空間換時間或者時間換空間。

更多關于復雜度的知識，我們會在后續數據結構和算法的設計與實現過程中穿插講解。

總結

以上是生活随笔為你收集整理的“算法复杂度”——其实并没有那么复杂的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。