為什么這個演算法要執行這么長時間？

今天應做的事沒有做，明天再早也是耽誤了， ——裴斯泰洛齊

你好，我是悅創，

最近真的有好久的時間沒有與讀者們想見，因為時間關系和不知道寫什么可以吸引到你們，想了好久，最終寫了此篇文章，感謝你們陪伴我走過了這段時間，就想寫個基礎，也是很多人不去寫的文章，

如果，你有閱讀我的文章會發現，我的文章都是非常的長的，耗費了很多心血，也希望這些文章對你們是有幫助的，

什么是時間復雜度

一個高級語言撰寫的程式的運行時間主要取決于三個因素：

• 演算法的方法，策略；
• 問題的輸入規模；
• 計算機執行指令的速度，

分析

1. 問題的輸入規模是客觀的、限定的，要加快演算法的效率絕不能影響問題的輸入規模，
2. 計算機執行指令的速度雖然可以有顯著提升，但其發展時間較長，也不是確定的，總不能終日盼著計算機性能的提升，
3. 所以提高演算法的效率，減少程式運行時間，改進演算法的策略是至關重要的，

在講解時間復雜度之前，需先引入一個概念， 時間頻度 ，

時間頻度代表一個演算法中的陳述句執行次數，其又可以被稱為 陳述句頻度 ，

顯然，時間頻度越高的演算法運行的時間越長，時間頻度也可被記為 T(n) ，其中 n 為問題的規模，即輸入值的規模，

時間復雜度的具體定義為：若有某個輔助函式 f(n) ，使得的 f ( n ) T ( n ) {f(n)} \over {T(n)} T(n)f(n)? 極限值（當 n 趨近于無窮大時)為不等于零的常數，則稱 f ( n ) f(n) f(n) 是 $ T(n)$ 的同數量級函式，記作： T ( n ) = O f ( n ) T(n) = Of(n) T(n)=Of(n) ，

稱 O ( f ( n ) ) O(f(n)) O(f(n)) 為演算法的漸進時間復雜度，簡稱時間復雜度，在數學上，大 O O O 符號用來描述一個函式數量級的漸近上界，

以上是純數學分析，看不太懂的讀者可以理解為時間復雜度就是演算法運行時間和輸入規模的關系，

時間復雜度是漸進的

如果我們將演算法中的一次計算記為 1 1 1 ，那么如果有 n n n 個輸入值，演算法對每一個輸入值做一次運算，那么整個演算法的運算量即為 n n n，這個時候，我們就可以說，這是一個時間復雜度為 O ( n ) O(n) O(n) 的演算法，

同理，如果仍有 n n n 個輸入值，但演算法對每一個輸入值做一次運算這個操作需要再重復 n n n 次，那么整個演算法的運算量即為 n ? n = n 2 n*n = n^2 n?n=n2，時間復雜度為 O ( n 2 ) O(n^2) O(n2) ，這時如果對每一個輸入值做一次運算這個操作需要重復 n + 1 n+1 n+1 次，演算法運算量變為：$ n*(n+1) = n^2+n $

這時的時間復雜度是否改變為 O ( n 2 + n ) O(n^2+n) O(n2+n) ？上文曾提到時間復雜度考察的是當輸入量趨于無窮時的情況，所以當 n n n 趨于無窮的時候， n 2 n^2 n2 對演算法運行時間占主導地位，而 n n n 在 $ n^2 $ 面前就無足輕重，不計入時間復雜度中，

換句話說，因為 n 2 + n n^2+n n2+n 漸近地（在取極限時）與 n 2 n^2 n2 相等，此外，就運行時間來說， n n n 前面的常數因子遠沒有輸入規模 $ n $ 的依賴性重要，所以是可以被忽略的，也就是說 $O(n^2) $ 和 是 O ( n 2 2 ) O(\frac{n^2}{2}) O(2n2?) 相同時間復雜度的，都為 O ( n 2 ) O(n^2) O(n2)，

時間復雜度分析

讓我們先看一段代碼：

def square(n):
    Partial_Sum = 0
    for i in range(1, n + 1):
        Partial_Sum += i * i
    return Partial_Sum

代碼的第二行只占一次運算，第三行的 for 回圈中 i 從 1 加到了 n，其中程序包括 i 的初始化， i 的累加，和 i 的范圍判斷，分別消耗 1 次運算，n 次運算，和 n+1 次運算，

至此，代碼的前三行共進行了 2 n + 3 2n+3 2n+3 次運算，第四行是相乘，相加，和賦值三個功能的組合的代碼，相乘所需 n 次運算，相加所需 n 次運算，而賦值也需 n 次運算，所以第四行一共進行了 3 x n 3xn 3xn 次運算，最后一行回傳消耗一次運算，

總體來看，這段代碼一共需進行 2 n + 3 + 3 n + 1 = 5 n + 4 2n+3+3n+1 = 5n+4 2n+3+3n+1=5n+4 次運算，根據上文的漸進原則，這段代碼的時間復雜度為 O ( n ) O(n) O(n)，

通過上面的分析，可以看出細致的時間復雜度分析十分繁瑣，但畢竟時間復雜度追求漸進原則，所以在這里為大家整理了一下快速算時間復雜度的技巧：

回圈結構

for i in range(1, k*n+m+1):
	i += 1

上示代碼中的 n 為輸入規模，k，m 均為已知常數，因此根據漸進原則，只要 for 回圈的回圈范圍是在 n 的有限倍數以內（range 的上界始終可以被表示為 $ k*m+n $ 的形式），則一個 for 回圈的時間復雜度必然為 O ( n ) O(n) O(n)，

for i in range(n):
	for j in range(n):
    	Partial_Sum += 1

我們將兩個 for 回圈迭代在一起，有 n 個不同的 i，每個i 會對應 n 的不同的 j 的情況下，會有 n ? n = n 2 n*n = n^2 n?n=n2 次第三行的操作，在這里我們可以說這段代碼的時間復雜度為 O ( n 2 ) O(n^2) O(n2)，實際上，真實的運算次數會有 k ? n 2 k*n^2 k?n2 次（k為一個常數），其中 k 始終是有限的盡管 k 有時會非常大，

綜上所述，我們可以總結出回圈結構時間復雜度的一些規律：

• 無論是 for 還是 while 回圈，只要回圈的范圍可以表示為 k ? n + m k * n + m k?n+m ，則該回圈的時間復雜度為 O ( n ) O(n) O(n)；
• 如果回圈中嵌套回圈，則時間復雜度將便成每一層回圈的時間復雜度相乘的結果；
• 在決定時間復雜度時，往往只需要關注層數最多 for 回圈結構的時間復雜度，因為其它回圈的時間復雜度很大可能上會被忽略，

遞回結構

def feb(n)
    if n <= 1:
        return 1
    else:
        return feb(n - 1) + feb(n - 2)

如上所示的是一個計算斐波那契數列函式，而我們都是道斐波那契數列的公式為：

f ( n ) = f ( n ? 1 ) + f ( n ? 2 ) f(n) = f(n-1)+f(n-2) f(n)=f(n?1)+f(n?2)

假設當輸入規模為時該函式的運行次數為 T ( n ) T(n) T(n) ，通過上示公式我們可以得到：

T ( n ) = ( T ( n ? 1 ) + 1 ) + ( T ( n ? 2 ) + 1 ) T(n) = (T(n-1)+1)+ (T(n-2)+1) T(n)=(T(n?1)+1)+(T(n?2)+1)

由于常數不會影響到函式整體的時間復雜度，所以可以被簡化為：

T ( n ) = T ( n ? 1 ) + T ( n ? 2 ) T(n) = T(n-1)+T(n-2) T(n)=T(n?1)+T(n?2)

到這一步，我們已經知道當輸入規模為n時，斐波那契數列函式時間復雜度的遞推公式，而我們只需求出通項公式即可分析出其時間復雜度為 O ( ( 1 + 5 2 ) n ) O((\frac{1+\sqrt5}{2})^n) O((21+5 ??)n)，約為 O ( 1.61 8 n ) O(1.618^n) O(1.618n)，簡化默認為指數級復雜度 O ( 2 n ) O(2^n) O(2n) ，可以看出，該斐波那契數列函式的時間復雜度成指數增長，說明這是較為低效的一個遞回函式，

小結

在了解演算法本質的同時，要掌握時間復雜度來判斷一個演算法的效率和實用性，相同問題時，演算法的復雜度越低，證明演算法的效率越高，本質上，輸入規模往往是對空間復雜度與時間復雜度影響最大的因素，對于時間復雜度來說，輸入量越多，所需處理的資料量越多，計算次數越多，演算法運行的時間越多，