時間複雜度

　　從比較執行時間的層面來看，或許你會想到：直接利用計時器來比較不同演算法實現程式的執行時間。但是，這種方式的變因太多。實作演算法的程式語言、記憶體大小、不同的編譯（直譯）器、甚至是電腦中運行的程式，可能都會影響計時所得的結果。相對的，這種方式也就顯得不太準確。

　　除了實際去計時之外，我們也可以假設演算法中「每一步」的執行時間都相同。於是，我們也可以直接拿演算法所有「步驟」的執行次數總和來進行比較。

時間複雜度(Time Complexity)的定義
　　演算法的時間複雜度(Time Complexity)O(f(n))是指 在最差情況（worst case）下执行演算法所須要的「步驟」數 的概量。

 T(n): 某演算法的執行時間 or 實際指令執行次數。通常和f(n)量級(order)相同。T(n)=O(f(n))。T(n) ∈ Ο(f(n))，就代表函數 T(n) 的成長趨勢與 f(n) 相似或是更慢的。

 f(n): 又可以稱為執行時間的成長率(rate of growth) ,T(n)的辅助函数。

 O(f(n)): 某演算法的時間複雜度, 可以看成是某一演算法在電腦中所需執行時間始終不會超過某一常數倍的f(n)(i.e. cf(n))。

 n: 輸入量, or 程式的规模。

又在此我們可以定義對輸入量n而言，程式的最大執行時間就是時間複雜度(Time complexity)的衡量標準。通常在漸近表示法(Asymptotic Notation)中，我們一般以Big-O來表示。

e.g. 

-T(n)=n^2+3n+4 和 T(n)=4n^2+2n+1 时间频度不同，但时间复杂度相同，都为O(n^2)，f(n)=n^2。

top

 
例：請問下面程式區段的迴圈部份實際執行次數及時間複雜度[C]
　#include <stdio.h>
　void main()
　{
　int i,j,k;
　for (i=1; i<=n ; i++)
　for (j=1; j<=n ; j++)
　for (k=1; k<=n ; k++)
　printf("%d %d %d \n",i,j,k);;;
　}
[Visual BASIC] 

　for i =1 to n
　for j= i to n
　for k=j to n
　…
　next k
　next j
　next i 

答： 這個問題是希望釐清同學對有關實際執行次數和時間複雜度在表現意義上的不同。在本題有關實際執行次數的問題，同學先要清楚是指那一道指令的次數。由於這題是「迴圈」執行的部份，毋需考慮迴圈內部指令的多寡。因此我們可用數學式來計算：

　　這個n(n+l)(n+2)/6就是實際的迴圈執行次數，且我們知道必定存在c，n0使得n(n+l)(n+2)/6≦cn³，當n≧n0時，時間複雜度為O(n³)。

top

 常見的Big-oh

1.O(1)或O(c)：稱為常數時間(constant time)

　　這表示演算法則的執行時間是一個常數倍，而忽略資料集合大小的變化。一個例子是在電腦中它存取RAM所花的時間，在記憶體中去讀取及寫入所用的時間是相同的，而不考慮整個記憶體的數量。如果有這樣的演算法則存在，則我們可以在任何大小的資料集合中自由的使用，而不需要擔心時間或運算的次數會一直成長或變得很高。

2. O(n)：稱為線性時間(linear time)

　　它執行的時間會隨資料集合的大小而線性成長。我們可以找到一個例子是在一個沒有排列過的資料集中要找一個最大元素，且我們以簡單的方式去解釋其內容，直到我們將所有的資料都找過並且找到最大值為止。

3.O(log₂n)：稱為次線性時間(sub-linear time)

　　這一種函式的成長速度比線性的程序還慢，而此常數(它是不成長的)的情形還快。

4.O(n²)：稱為平方時間(quadratic time)

　　演算法則執行時間會成二次方的成長，這種會變得不切實際，特別是當資料集合的大小變得很大時。

5.O(n³)：稱為立方時間(cubic time)

6.O(2ⁿ)：稱為指數時間(exponential time)

7.O(n1og₂n)：介於線性及二次方成長的中間之行為模式。

top

 何謂Ω(omega)
　　除了Big-oh可以視為計算機時間複雜度的最壞表現之外，我們還要認識所謂的Ω(omega)，它也是一種時間的漸近表示法。

定義：f(n)=Ω(g(n))，若且唯若存在大於0的常數c和n0，使得對所有n值而言，n≧n0時，f(n)≧cg(n)均成立。

換句話說，對於f(n)=Ω(g(n))而言，g(n)就可以看成是f(n)的下限，也就是對f(n)=Ω(g(n))而言，g(n)就是它成長的最大函數。

top

 何謂Θ(Theta) 
　　 另外一種在本書中將介紹的漸近表示法稱為Θ(Theta)。它和"big-oh"及"Omega"比較而言，是一種更為精確的方法。它的定義如下:

定義：f(n)=Θ(g(n))，若且唯若存在大於0的常數c1,c2和n0，使得對所有n值而言，n≧n0時，c1g(n)≦f(n)≦c2g(n)均成立。

事實上f(n)=Θ(g(n))，就是g(n)可同時代表f(n)的上限和下限。我們再以3n+2的例子說明：

　當n≧2時，3n+2≦4n即3n+2=O(n)
　當n≧l時，3n+2≧3n即3n+2=Ω(n)
　則我們就可以做成以下的結論3n+2=Θ(n)。

　　 對於使用漸近式表示法來描述時間複雜度到底那一種是最佳的方法?在前面我們就指出了"big-oh"是對演算法的時間複雜度描述最常用的表示法。原因就是在漸近表示法中我們通常只關切其最大項目(leading term)的原因。