轉載自 這裡
時間複雜度(Time Complexity)的定義 :
在程式設計中，決定某程式區段的步驟計數是程式設計師在控制整體程式系統時間的重要因素，不過要決定精確的次數卻也真是一困難的工作。特別是在不確定型(如指令x=l和x=x2+x3.15/x-4)比較，雖然我們都將其視為一個指令，不過運用的複雜程度理所當然影響了真正精確的執行時間。由此得知花費很大的功夫去計算真正的執行次數是沒有意義的。所以我們往往以一種「概量」的精神來做為衡量的準則，稱為「時間複雜度」(Time complexity)。按著我們就來看它的詳細介紹:
我們定義一個T(n)，表示在一個完全理想狀態的計算機中程式所執行的實際指令次數。一個程式的執行時間並不完全和輸入量有關，演算法的好壞也會影響，所以我們可以把它當作輸入量為n的一種函數。又在此我們可以定義對輸入量n而言，它的最大執行時間就是時間複雜度(Time complexity)的衡量標準。通常在漸近表示法(Asymptotic Notation)中，我們一般以Big-oh來表示。
何謂Big-oh :
O(f(n))可以看成是某一演算法在電腦中所需執行時間始終不會超過某一常數倍的f(n)。更清楚的說就是若某演算法的執行時間T(n)的時間複雜度是O(f(n))，意謂存在兩個常數c與n0，若n≧n0，則T(n)≦cf(n)。f(n)又可以稱為執行時間的成長率(rate of growth)。為了增加同學的了解，我們趕快來看看有關的一些例子。
例如，假設某些程序詳細分析後得到的結果是其運算的次數與參數n有關，如下：
N(n)=3n2+11n-45
在這個多項式中會主導整個函式且成長最快的是n2項，一般而言，在一個多項式中會主導的項是具有最高次的那一項。用一個表來說明這個表示式中值的成長是n在主導的，如下的表所示。從這個表我們可以觀察到只使用n2項而不是使用整個公式時，它會隨著n變大而與正確值的誤差百分比會非常小。這主要是因為這個項的成長比其他二個項的成長還要快速，這二個項因此可以被忽略。我們可以說對於較大的n值，這個副程式基本上是一個3n2的處理程序。
例：請問下面程式區段的迴圈部份實際執行次數及時間複雜度
[C]
[Visual BASIC]
答： 這個問題是希望釐清同學對有關實際執行次數和時間複雜度在表現意義上的不同。在本題有關實際執行次數的問題，同學先要清楚是指那一道指令的次數。由於這題是「迴圈」執行的部份，毋需考慮迴圈內部指令的多寡。因此我們可用數學式來計算：
這個n(n+l)(n+2)/6就是實際的迴圈執行次數，且我們知道必定存在c，n0使得n(n+l)(n+2)/6≦cn3，當n≧n0時，時間複雜度為O(n3)。
常見的Big-oh :
對於比較2個不同的時間複雜度，千萬不可以用直觀的方法來判斷。例如有2種演算法，時間複雜度各為O(n)與O(n2)。如果這2種方法的實際執行次數T'(n)=2n，T"(n)=n2，則n>2時，2n
1.O(1)或O(c)：稱為常數時間(constant time)
這表示演算法則的執行時間是一個常數倍，而忽略資料集合大小的變化。一個例子是在電腦中它存取RAM所花的時間，在記憶體中去讀取及寫入所用的時間是相同的，而不考慮整個記憶體的數量。如果有這樣的演算法則存在，則我們可以在任何大小的資料集合中自由的使用，而不需要擔心時間或運算的次數會一直成長或變得很高。
2. O(n)：稱為線性時間(linear time)
它執行的時間會隨資料集合的大小而線性成長。我們可以找到一個例子是在一個沒有排列過的資料集中要找一個最大元素，且我們以簡單的方式去解釋其內容，直到我們將所有的資料都找過並且找到最大值為止。
3.O(log2n)：稱為次線性時間(sub-linear time)
這一種函式的成長速度比線性的程序還慢，而此常數(它是不成長的)的情形還快。
4.O(n2)：稱為平方時間(quadratic time)
演算法則執行時間會成二次方的成長，這種會變得不切實際，特別是當資料集合的大小變得很大時。
5.O(n3)：稱為立方時間(cubic time)
6.O(2n)：稱為指數時間(exponential time)
7.O(n1og2n)
介於線性及二次方成長的中間之行為模式。
何謂Ω(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)就是它成長的最大函數。
何謂Θ(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的例子說明：
對於使用漸近式表示法來描述時間複雜度到底那一種是最佳的方法?在前面我們就指出了"big-oh"是對演算法的時間複雜度描述最常用的表示法。原因就是在漸近表示法中我們通常只關切其最大項目(leading term)的原因。
時間複雜度(Time Complexity)的定義 :
在程式設計中，決定某程式區段的步驟計數是程式設計師在控制整體程式系統時間的重要因素，不過要決定精確的次數卻也真是一困難的工作。特別是在不確定型(如指令x=l和x=x2+x3.15/x-4)比較，雖然我們都將其視為一個指令，不過運用的複雜程度理所當然影響了真正精確的執行時間。由此得知花費很大的功夫去計算真正的執行次數是沒有意義的。所以我們往往以一種「概量」的精神來做為衡量的準則，稱為「時間複雜度」(Time complexity)。按著我們就來看它的詳細介紹:
我們定義一個T(n)，表示在一個完全理想狀態的計算機中程式所執行的實際指令次數。一個程式的執行時間並不完全和輸入量有關，演算法的好壞也會影響，所以我們可以把它當作輸入量為n的一種函數。又在此我們可以定義對輸入量n而言，它的最大執行時間就是時間複雜度(Time complexity)的衡量標準。通常在漸近表示法(Asymptotic Notation)中，我們一般以Big-oh來表示。
何謂Big-oh :
O(f(n))可以看成是某一演算法在電腦中所需執行時間始終不會超過某一常數倍的f(n)。更清楚的說就是若某演算法的執行時間T(n)的時間複雜度是O(f(n))，意謂存在兩個常數c與n0，若n≧n0，則T(n)≦cf(n)。f(n)又可以稱為執行時間的成長率(rate of growth)。為了增加同學的了解，我們趕快來看看有關的一些例子。
例如，假設某些程序詳細分析後得到的結果是其運算的次數與參數n有關，如下：
N(n)=3n2+11n-45
在這個多項式中會主導整個函式且成長最快的是n2項，一般而言，在一個多項式中會主導的項是具有最高次的那一項。用一個表來說明這個表示式中值的成長是n在主導的，如下的表所示。從這個表我們可以觀察到只使用n2項而不是使用整個公式時，它會隨著n變大而與正確值的誤差百分比會非常小。這主要是因為這個項的成長比其他二個項的成長還要快速，這二個項因此可以被忽略。我們可以說對於較大的n值，這個副程式基本上是一個3n2的處理程序。
例：請問下面程式區段的迴圈部份實際執行次數及時間複雜度
[C]
- #include
- 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);;;
- }
- 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≦cn3，當n≧n0時，時間複雜度為O(n3)。
常見的Big-oh :
對於比較2個不同的時間複雜度，千萬不可以用直觀的方法來判斷。例如有2種演算法，時間複雜度各為O(n)與O(n2)。如果這2種方法的實際執行次數T'(n)=2n，T"(n)=n2，則n>2時，2n
1.O(1)或O(c)：稱為常數時間(constant time)
這表示演算法則的執行時間是一個常數倍，而忽略資料集合大小的變化。一個例子是在電腦中它存取RAM所花的時間，在記憶體中去讀取及寫入所用的時間是相同的，而不考慮整個記憶體的數量。如果有這樣的演算法則存在，則我們可以在任何大小的資料集合中自由的使用，而不需要擔心時間或運算的次數會一直成長或變得很高。
2. O(n)：稱為線性時間(linear time)
它執行的時間會隨資料集合的大小而線性成長。我們可以找到一個例子是在一個沒有排列過的資料集中要找一個最大元素，且我們以簡單的方式去解釋其內容，直到我們將所有的資料都找過並且找到最大值為止。
3.O(log2n)：稱為次線性時間(sub-linear time)
這一種函式的成長速度比線性的程序還慢，而此常數(它是不成長的)的情形還快。
4.O(n2)：稱為平方時間(quadratic time)
演算法則執行時間會成二次方的成長，這種會變得不切實際，特別是當資料集合的大小變得很大時。
5.O(n3)：稱為立方時間(cubic time)
6.O(2n)：稱為指數時間(exponential time)
7.O(n1og2n)
介於線性及二次方成長的中間之行為模式。
何謂Ω(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)就是它成長的最大函數。
何謂Θ(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的例子說明：
對於使用漸近式表示法來描述時間複雜度到底那一種是最佳的方法?在前面我們就指出了"big-oh"是對演算法的時間複雜度描述最常用的表示法。原因就是在漸近表示法中我們通常只關切其最大項目(leading term)的原因。
This message was edited 4 times. Last update was at 16/03/2010 14:57:38
沒有留言:
張貼留言