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

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

你好，我是悅創。

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

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

什麼是時間複雜度

一個高階語言編寫的程式的執行時間主要取決於三個因素：

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

分析

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

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

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

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

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

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

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

時間複雜度是漸進的

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

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

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

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

時間複雜度分析

讓我們先看一段程式碼：

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 次運算。

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

總體來看，這段程式碼一共需進行 $2n+3+3n+1=5n+4$ 次運算。根據上文的漸進原則，這段程式碼的時間複雜度為 $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)$。

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

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

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

• 無論是 for 還是 while 迴圈，只要迴圈的範圍可以表示為 $k\ast n+m$ ，則該回圈的時間複雜度為 $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)$$

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

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

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

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

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

小結

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