討論區快速選單
知識庫快速選單
程式設計俱樂部Facebook粉絲團 網路投保旅行平安險 討論區最近新進100則主題
[ 回上頁 ] [ 討論區發言規則 ]
法則分析 (演算法)
更改我的閱讀文章字型大小
作者 : chiuinan2(青衫)討論區板主 Visual C++ .NET卓越專家VC++一代宗師Visual Basic優秀好手資訊類作業求救卓越專家一般曠世奇才程式設計甘苦談優秀好手C++ Builder優秀好手上班族的哈拉園地優秀好手C++頂尖高手Assembly優秀好手貼文超過3000則人氣指數超過150000點
[ 貼文 3732 | 人氣 170106 | 評價 34520 | 評價/貼文 9.25 | 送出評價 125 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2004/10/8 下午 10:04:58
法則分析(The Design and Analysis of Computer Algorithms)

前言

法則分析,有時直接稱之為演算法(Algorithm),是一門用來學習如何解決問題,以及分析解題方法效率的學問。由於在學法則分析時,通常都會學到許多問題的解法(即演算法),因此直接將它視為學習演算法的學問也成。法則分析對於程式設計師與系統設計師是很重要的,如果不懂法則分析,對於一些常見的問題,往往不知有更有效率的演算法,同時也無法分析自己提出的演算法之效率性,因此讀者最好多多研究這門學問。在本文中,作者主要的目標是在說明各種解題的方法,並舉例說明其應用方式,以及所得演算法的效率分析。對於一般常見問題的演算法,如排序、搜尋等,將另以專文介紹說明。另外,法則分析中關於演算法Lower Bound、Upper Bound(即找出演算法最佳與最差的效率極限),以及NP問題(即很難找到有效演算法的問題),由於太偏學術性研究,因此在本文中也省略不提。

邱奕南,2001/4/17



演算法效率的分析

演算法的效率分析,大致可分為時間效率和空間效率兩種,一般以O記號來表示,稱為該演算法的Order。其正式定義為:

一個演算法其執行所需的時間或空間為f(n),而其Order為g(n),n為輸入資料的數目,則存在常數c和m,使得f(n) <= c*g(n),當n > m時。

例如一個演算法的時間效率為O(n^2),表示當輸入的資料量為n時,執行該演算法所需的時間會以n^2的倍率成長。因此當再出現另一種演算法其時間效率為O(nlogn)時,由於nlogn<n^2(當n夠大時),因此新的演算法便被認為比原來的演算法來得有效率。注意演算法效率的比較,還分成平均情況(average case)和最糟情況(worst case)兩種,平均情況較佳者,在實際運用上的效率通常也較佳,不過仍必須考量最糟情況出現的比例。

分析效率時,必須針對演算法中最費時間或最耗記憶體的部份進行分析,例如排序或搜尋演算法中,大都以比對元素(comparison)的次數為準進行分析,又例如傅立葉轉換(Fourier Transform),則以乘法的次數為準。至於如何計算出一個演算法的Order,由於牽涉到演算法的內容,因此我們會在後面提到的例子中,再加以列出說明。不過此處我們先列出一些常見的分析相關式,讀者可和後面的例子對照了解,對於將來在分析演算法的效率上是很有用的:

1. T(n) = aT(n/c) + bn

T(n) = O(n), if a < c
T(n) = O(nlogn), if a = c
T(n) = O(n^logca), if a > c

2. T(n) = aT(n/c) + bn^2

T(n) = O(n^2), if a < c^2
T(n) = O(n^2 logn), if a = c^2
T(n) = O(n^logca), if a > c^2

以下我們便開始一一說明各種解題的方法。
作者 : chiuinan2(青衫)討論區板主 Visual C++ .NET卓越專家VC++一代宗師Visual Basic優秀好手資訊類作業求救卓越專家一般曠世奇才程式設計甘苦談優秀好手C++ Builder優秀好手上班族的哈拉園地優秀好手C++頂尖高手Assembly優秀好手貼文超過3000則人氣指數超過150000點
[ 貼文 3732 | 人氣 170106 | 評價 34520 | 評價/貼文 9.25 | 送出評價 125 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2004/10/8 下午 10:05:44
一、直覺法

直覺法,便是依照人類最直覺的思考模式去找出問題的解法。這種方法往往都能找出可解決問題的演算法,尤其是面對從未遇過的問題類型的情況下。只不過以這種方式找出的演算法,其效率通常都不怎麼好。

例1:插入排序法(Insertion Sort)

想想看我們在玩撲克牌時是怎麼排序的?假設現在手上的牌已經依照花色和數字排好,再拿到一張牌時,我們會依序比較各個牌,找到適當的位置後再插入,插入排序法的觀念便和這種方式相同。假設目前已有n-1個排好的資料,再加入一個資料時,最糟的情況下,我們會比對n-1次才能找到要插入的位置,因此其時間效率T(n)為:

T(n) = T(n-1) + n-1 = T(n-2) + n-2 + n-1 = ... = T(1) + 1 + ... + n-1 = T(1) + n*(n-1)/2

由於T(1)是個常數,因此取其最高次項,可得知其時間效率為O(n^2)。

例2:線性搜尋法(Linear Search)

在資料搜尋時,最直覺的方式便是一個一個找,一定能夠找到。於是在n個資料中搜尋時,在最糟的狀況下,我們必須比對n次,因此其時間效率為O(n)。

例3:矩陣乘法

對於兩個nxn的矩陣A和B相乘,最直覺的方式便是將它展開起來運算,於是我們需要n^3次乘法和(n-1)*n^2次加法,因此其時間效率為O(n^3)。

作者 : chiuinan2(青衫)討論區板主 Visual C++ .NET卓越專家VC++一代宗師Visual Basic優秀好手資訊類作業求救卓越專家一般曠世奇才程式設計甘苦談優秀好手C++ Builder優秀好手上班族的哈拉園地優秀好手C++頂尖高手Assembly優秀好手貼文超過3000則人氣指數超過150000點
[ 貼文 3732 | 人氣 170106 | 評價 34520 | 評價/貼文 9.25 | 送出評價 125 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2004/10/8 下午 10:06:32
二、分割解決法(Divide and Conquer)

分割解決法是解決一般問題最有效率的方法。它先將問題分割成數個相同類型的小問題,然後再針對各個小問題找出解法,最後再將各小問題的答案綜整成整個問題最終的答案,因此使用這種方法找出的演算法,通常會運用到大量的遞迴呼叫(recursive call)。利用分割解決法所找出的演算法,只要在合併的效率上多加考量,則它的效率一般都會有不錯的表現。

例1:合併排序法(Merge Sort)

Merge Sort的概念,是將所有元素分成相同數目的兩堆,然後用遞迴的方式將這兩堆排好,最後再將這兩堆排好的元素合併排好。由於兩堆n/2數目的已排好元素要合併排好,其比對的次數為cn,c為一常數,因此可分析其時間效率T(n)為:

T(n) = 2T(n/2) + cn = 4T(n/4) + 2cn = 8T(n/8) + 3cn = ... = nT(1) + logn*cn

取其最高次項得知其時間效率為O(nlogn)。

例2:矩陣乘法

對於兩個nxn的矩陣A和B相乘,我們可將矩陣A和B分割成4個n/2xn/2子矩陣如下:

[A11 A12] [B11 B12]   [C11 C12]
[       ] [       ] = [       ]
[A21 A22] [B21 B22]   [C21 C22]

其中

C11 = A11*B11 + A12*B21
C12 = A11*B12 + A12*B22
C21 = A21*B11 + A22*B21
C22 = A21*B12 + A22*B22

若以乘法次數來分析,則其時間效率T(n)為:

T(n) = 8T(n/2) = 8^2 T(n/4) = 8^3 T(n/8) = ... = 8^logn T(1) = n^3 T(1)

可得知時間效率仍為O(n^3),一點都沒有改善。但如果我們改良上述合併的方式成為:

m1 = (A12-A22)(B21+B22)
m2 = (A11+A22)(B11+B22)
m3 = (A11-A21)(B11+B12)
m4 = (A11+A12)B22
m5 = A11(B12-B22)
m6 = A22(B21-B11)
m7 = (A21+A22)B11
C11 = m1+m2-m4+m6
C12 = m4+m5
C21 = m6+m7
C22 = m2-m3+m5-m7

也就是多利用加法來少掉乘法的計算(因為乘法速度較慢),如此T(n) = 7T(n),可得到其時間效率為O(n^log7),約為O(n^2.81)。之後有人又提出其他的算法,可減少加法的次數,但乘法至少仍須7次,這點也已被人用數學證明了。然而這並不是這個演算法的極限,因為之後還有人使用不同的方法來解這個問題,而得到了一個O(n^2.734)的演算法。

例3:挑出n個數中的最大值和最小值

如果我們以直覺的方式先挑出最大值,再挑出最小值,則一共需要2n-3次比對,但若以分割解決法將之分成數量相同的兩堆,再從各堆中取出最大值和最小值,最後再從兩個最大值與兩個最小值去取得最大值與最小值,其所需的比對數為:

T(n) = 2T(n/2) + 2 = 4T(n/4) + 4 + 2 = ... = n/2 T(2) + n/2 + ... + 2

由於T(2)=1,因此T(n) = 3n/2 - 2。雖然兩者的Order都是O(n),但使用分割解決法的效率仍然比直覺法來得好。

例4:快速排序法(Quick Sort)

Quick Sort的觀念,是隨便取一個元素a,然後將比a小的元素放在一堆,比a大的元素放在一堆,接著利用遞迴的方式依次將這兩堆元素排好。在最糟的情況下,所有剩下的元素都是在同一堆中,因此其時間效率T(n)為:

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

由此解得T(n) = O(n^2)。不過快速排序法之所以被稱為快速,不是在它的最糟情況下,而是在平均情況下,它的比較次數會比其他排序法來得少。假設元素a出現在排好元素列中的各位置,其機率都是相同的,則:

T(n) = Σ(T(k-1)+T(n-k)) / n + n-1

解之得T(n) = O(nlogn)(過程略,有心的讀者可仔細推算)。

例5:Horner's rule

Horner's rule是將一個多項式f(x) = a(n) x^n + ... + a(1) x + a(0),以f(x) = f'(x)*x + a(0)的方式遞迴計算,如此可得到乘法的次數為:

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

得到T(n) = O(n)。事實上,Horner's rule在通用的情況下,已被證明其所需的乘法和加法都是最少的。

作者 : chiuinan2(青衫)討論區板主 Visual C++ .NET卓越專家VC++一代宗師Visual Basic優秀好手資訊類作業求救卓越專家一般曠世奇才程式設計甘苦談優秀好手C++ Builder優秀好手上班族的哈拉園地優秀好手C++頂尖高手Assembly優秀好手貼文超過3000則人氣指數超過150000點
[ 貼文 3732 | 人氣 170106 | 評價 34520 | 評價/貼文 9.25 | 送出評價 125 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2004/10/8 下午 10:07:02
三、刪減搜尋法(Prune and Search)

刪減搜尋法,是在有多個可能通到答案的路徑上,依照目前得到的特性值,事先去除一些不可能的路徑,再由目前剩下的路徑繼續嘗試搜尋。它的精神所在便是如何有效地刪減路徑,就像分割解決法強調的如何有效的合併一樣。不過由於利用刪減搜尋法得出來的演算法,有時會和分割解決法所得的結果相同,因此這兩種方法也時常被混淆在一起。

例1:二分搜尋法(Binary Search)

對於一個已排序好的n個元素,要找到某個元素,最好的方法便是取正中間的元素進行比較,如此便可去除一半的元素不必再比較。依此可得到其時間效率為:

T(n) = T(n/2) + 1

得到T(n) = O(logn)。

例2:挑第k個元素(kth Selection)

在n個數中挑選第k個最小的元素,若是先排序好再挑選,則最少需O(nlogn),若以刪減搜尋法,先隨便挑出一個元素a出來,然後將比a小的放到S1中,和a相同的放到S2中,比a大的放到S3中。接著查看S1、S2、S3的元素數目,如果k落在S1中,則只要繼續找S1便可以了;若落在S2中,元素a便是所要的結果;若落在S3,表示S1、S2裡面的元素都不可能了,修正k值再繼續找S3。如此在最糟的情況下,其時間效率為:

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

解之得T(n) = O(n^2)。不過在平均情況下,其時間效率是O(n)(由於解出過程頗複雜,在此省略,可參考前述之Quick Sort平均情況下的時間效率公式)。如果要增加最糟情況下的效率,最好的方法便是儘量挑到位在中央的元素a,如此才能刪減掉最多的元素。以下便是一種挑選方法:

將元素每r個分成一堆,r最好取5,7,9等較小的奇數(不可取3)。
對每堆元素,找出其實際的中央元素,組合成另一堆元素。
針對前述所得之元素堆,以遞迴方式繼續取得近似中央元素。
在數理上可證明由此方法得出的元素,至少有n/4個元素比它小,且至少有n/4個元素比它大,於是最糟情況下的時間效率函數,可寫成(第一個式子為挑近似中央元素,第二個式子為挑第k個元素):

T(n) = [crn + T(n/r)] + [cn + T(3n/4)] = T(n/r) + T(3n/4) + cn

因此只要n/r+3n/4 < n,便可推得T(n) = O(n),這也是為什麼r必須挑選5以上奇數的原因。不過雖然最糟情況下的效率改善了,但由於這個挑選過程也必須花不少時間,因此它的平均效率反而也因此而下降。

作者 : chiuinan2(青衫)討論區板主 Visual C++ .NET卓越專家VC++一代宗師Visual Basic優秀好手資訊類作業求救卓越專家一般曠世奇才程式設計甘苦談優秀好手C++ Builder優秀好手上班族的哈拉園地優秀好手C++頂尖高手Assembly優秀好手貼文超過3000則人氣指數超過150000點
[ 貼文 3732 | 人氣 170106 | 評價 34520 | 評價/貼文 9.25 | 送出評價 125 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2004/10/8 下午 10:07:30
四、分支限制法(Branch and Bound)

分支限制法和刪減搜尋法的概念很像,都是利用刪減路徑的方式來增加演算法的效率,只是刪減搜尋法大都用在單層路徑的搜尋上,而分支限制法則是用在決策樹展開的情況,可說是一種全面搜尋(exhaustive search)的方法。利用分支限制法來找決策問題的答案,首先必須定義出一個決策路徑的評價函數(evalue function),而我們所要找的,便是評價值最高的決策路徑。接著必須定出評價函數的下限函數(lower bound function)與上限函數(upper bound function),這兩個函數關係著分支限制法的效率,將之定義如下:

評價函數 = e(x)
下限函數 = c(x)
上限函數 = u(x)



c(x) <= e(x) <= u(x) ,對於決策樹中每個節點x

這三個函數的作用方法是這樣子的。當搜尋到某個節點a時,在還沒搜尋完a的所有子樹前,它的e(a)是未知的(因為不知決策的結果),但我們可以估算出這個值介於c(a)與u(a)之間,於是展開a的下一層,挑選下限函數c(x)估算值最大的子樹以遞迴方式展開搜尋(因所得結果最不會偏低),最後得到該子樹中最佳決策路徑的評價值e,這也是目前a的最佳評價值(如果已有其他下層子樹展開過,則取最大值),於是a其他的下層子樹,凡是上限函數u(x)估算值不超過e的,便可以刪減而不必再展開了(因為根本不可能再提升a的評價值),如此便可達到加快搜尋速度的效果。

分支限制法的另一種運用,便是棋類遊戲的決策,稱為遊戲樹搜尋(Game Tree Search)。由於棋類遊戲大都採一來一往的方式進行,因此每一層所要挑的評價值便時大時小,亦即奇數層(己方下時)要大,而偶數層(敵方下時)要小,因此前述的下限函數和上限函數的角色便會隨著層數的不同而角色互換,一般統稱為alpha-beta pruning。關於Game Tree Search的實作方式,一般資料結構的書藉都有提到,有興趣的讀者可去研究看看。

作者 : chiuinan2(青衫)討論區板主 Visual C++ .NET卓越專家VC++一代宗師Visual Basic優秀好手資訊類作業求救卓越專家一般曠世奇才程式設計甘苦談優秀好手C++ Builder優秀好手上班族的哈拉園地優秀好手C++頂尖高手Assembly優秀好手貼文超過3000則人氣指數超過150000點
[ 貼文 3732 | 人氣 170106 | 評價 34520 | 評價/貼文 9.25 | 送出評價 125 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2004/10/8 下午 10:08:47
五、貪心法(Greedy Method)

貪心法,是在面對一堆可能通到答案的決策路徑時,直接選擇目前最有可能的路徑下去尋找,其要點在於如何決定最有可能的路徑。在實際運用上,貪心法幾乎很少能夠成功地找到正確答案的,不過它卻往往可以得到一個不錯的近似答案,而且其時間效率通常也非常的好。

例1:Knapsack問題

給定n個工作,其效益分別為p1∼pn,成本分別為w1∼wn,挑選m個工作,使得其成本總和小於C,而效益和最大。以貪心法來處理,可考慮:

1.由效益最大的開始挑起:不成功!
2.由成本最小的開始挑起:不成功!
3.由成本效益比pi/wi最大的開始挑起:成功!

於是得到一個O(nlogn)(依成本效益比排序)的最佳演算法(此部份可以加以證明,但不是本文所要強調的重點)。

例2:Minimum Cost Spanning Tree

對於一個無方向性圖形,給予每個邊緣一個成本值,找出具有最小成本總和,且可以連接所有端點的圖形邊緣集合。利用貪心法,便是直接挑選成本值最小的邊緣,只要加入時不會造成圖形有封閉循環的狀況,即可將該邊緣加入集合中。其時間效率為O(nlogn),n為邊緣數目。

例3:最短路徑(Shortest Path)

對於一個有方向性圖形,給予每個邊緣一個成本值,找出由一端點到另一端點,且具有最小成本總和的邊緣集合。這個問題若以貪心法,直接選連接目前端點最小成本的邊緣往前走,是無法得到正確答案的,必須稍加修改貪心原則才行。其演算法如下:

1.將所有端點的成本總和值設為無限大,並設定起始端點為目前端點。
2.以目前端點為基準,找出可由目前端點通往的所有下個端點,並計算由目前端點至下個端點之成本總和值。若該總和值比原下個端點記錄的總和值小,便重設下個端點記錄的總和值為新值。
3.從尚未拜訪過的端點中,挑出成本總和值最小者視為目前端點,重複步驟2,直到遇到終止端點為止。

其實這個過程可視為端點集合的擴展,不斷計算並尋找鄰近最小成本值總和的下個端點加入集合,直到遇到目的端點為止。其時間效率為O(n^2),n為端點數目。

作者 : chiuinan2(青衫)討論區板主 Visual C++ .NET卓越專家VC++一代宗師Visual Basic優秀好手資訊類作業求救卓越專家一般曠世奇才程式設計甘苦談優秀好手C++ Builder優秀好手上班族的哈拉園地優秀好手C++頂尖高手Assembly優秀好手貼文超過3000則人氣指數超過150000點
[ 貼文 3732 | 人氣 170106 | 評價 34520 | 評價/貼文 9.25 | 送出評價 125 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2004/10/8 下午 10:09:25
六、動態規劃法(Dynamic Programming)

動態規劃法最常用在決策類型的問題上,基本上它也是屬於全面搜尋的方式,可區分為前推法(Forward Approach)和後推法(Backward Approach)兩種。前推法是從問題開始往答案推進,而後推法則是從答案開始往問題推進。以前推法為例,假設目前已前進到決策點S,若要繼續往前找到答案,可將S視為問題,採用遞迴的方式繼續往前處理,因此最後呈現的結果,反而是由答案處開始運算回問題處,以找到最佳的決策路徑。而這種方法最難的地方,便是找出前一個最佳決策點與下一個最佳決策點之間的遞迴關係(recurrence relation)。

例1:Multistage Graph Problem

對於一個無方向性圖形,由起點s到終點t,所有路徑均為k條,給予每個邊緣一個成本值,找出由起點s到終點t,具有最小成本總和的路徑。這個問題可以將它看成是k階的決策路徑問題(但決策與決策間有交互關係,而非樹狀),以動態規劃法來解,首先定義它的遞迴關係式。假設Cost(i,j)為第i階的端點(決策點)j到終點t的最小成本總和,而c(j,l)為端點j到端點l的邊緣成本值,則:

Cost(i,j) = min { c(j,l) + Cost(i+1,l) } ,對於所有在第i+1階的端點l,且存在<j,l>的邊緣

遞迴結束的狀況便是:

Cost(k-1,j) = c(j,t) if 邊緣<j,t>存在,或無限大 if 邊緣<j,t>不存在

然後以Cost(1,s)進行遞迴計算,在計算過程中,即可找出最佳的路徑,其時間效率為O(n+e),n為端點數目,e為邊緣數目。

作者 : chiuinan2(青衫)討論區板主 Visual C++ .NET卓越專家VC++一代宗師Visual Basic優秀好手資訊類作業求救卓越專家一般曠世奇才程式設計甘苦談優秀好手C++ Builder優秀好手上班族的哈拉園地優秀好手C++頂尖高手Assembly優秀好手貼文超過3000則人氣指數超過150000點
[ 貼文 3732 | 人氣 170106 | 評價 34520 | 評價/貼文 9.25 | 送出評價 125 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2004/10/8 下午 10:09:57
結語

除了上述的解題方法外,其實還有其他的解題法,例如局部搜尋法(Local Search)、解線性規劃問題(Linear Programming)的單工法(Simplex Method)、以及數值分析常用的逼近法等,這些有的會另以專文說明,有的則偏於複雜,甚少用到,不值得在此處大費周章的說明。

參考文獻

1. Fundamentals of Data Structures, Ellis Horowitz, 1984, 松崗
2. Combinatorial Optimization: Algorithms and Complexity, Christos H.Papadimitriou, 1982, 儒林
3. Algorithms, Rebert Sedgewick, 1983, 東南
4. Algorithms + Data Structures = Programs, Niklaus Wirth, 1976, 儒林
5. The Design and Analysis of Computer Algorithms, Aho, 1974, 開發
作者 : chiuinan2(青衫)討論區板主 Visual C++ .NET卓越專家VC++一代宗師Visual Basic優秀好手資訊類作業求救卓越專家一般曠世奇才程式設計甘苦談優秀好手C++ Builder優秀好手上班族的哈拉園地優秀好手C++頂尖高手Assembly優秀好手貼文超過3000則人氣指數超過150000點
[ 貼文 3732 | 人氣 170106 | 評價 34520 | 評價/貼文 9.25 | 送出評價 125 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2004/10/8 下午 10:12:18
本文是我以前整理出來, 供非資訊本科出身的下屬參考學習用, po出來供大家參考. 本來還想再整理一些專文, 如排序, 搜尋, 數值分析等等的專論, 但後來工作一忙就擱下了...
作者 : peikai(peikai)
[ 貼文 15 | 人氣 151 | 評價 30 | 評價/貼文 2 | 送出評價 1 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2004/12/27 下午 04:05:01
推推推...這麼好的文章一定要推!
作者 : sim0831(翔) 人氣指數超過10000點
[ 貼文 134 | 人氣 18127 | 評價 260 | 評價/貼文 1.94 | 送出評價 11 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2004/12/30 下午 04:18:38
我是資訊系的...但我就是看不懂= =
如果我用C寫一個九九乘法表的話,
也需要用到演算法嘛?
作者 : sdanley(阿正)
[ 貼文 32 | 人氣 3308 | 評價 10 | 評價/貼文 0.31 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2004/12/30 下午 04:20:36
我很努力在看演算法但一個努力結果還是不懂>"<~不過還是要推....
作者 : yama99(lansan)
[ 貼文 8 | 人氣 176 | 評價 50 | 評價/貼文 6.25 | 送出評價 0 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2005/1/11 下午 10:42:22
十分感謝大大的分享。
小弟正是非資訊本科的,目前自學vb,
拜讀大作,獲益良多。
作者 : chiuinan2(青衫)討論區板主 Visual C++ .NET卓越專家VC++一代宗師Visual Basic優秀好手資訊類作業求救卓越專家一般曠世奇才程式設計甘苦談優秀好手C++ Builder優秀好手上班族的哈拉園地優秀好手C++頂尖高手Assembly優秀好手貼文超過3000則人氣指數超過150000點
[ 貼文 3732 | 人氣 170106 | 評價 34520 | 評價/貼文 9.25 | 送出評價 125 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2009/6/18 下午 04:59:45
附錄 - Quick Sort平均情況的時間複雜度

Quick Sort平均情況的時間複雜度公式如下:

T(n) = Σ(T(k-1)+T(n-k)) / n + cn, k=1∼n, c為一常數

這個公式應該不難理解。Quick Sort是任挑一個元素,然後再對剩下的元素進行大小分堆,然後遞迴下去排好兩堆元素。分堆需要掃過一遍全部元素,因此需要cn的時間。分堆的情況,各種可能都有,亦即剩下的n-1個元素可任意分成兩堆,因此將各種可能的分堆情況的時間總和起來,再加以平均,就是平均情況的時間複雜度。

由於在Σ的兩個時間T,一個是由0遞增到n-1,一個是由n-1遞減到0,對於加總而言,兩者其實可說是相同的序列,因此可合併為:

T(n) = 2 Σ(T(i)) / n + cn, i=0∼n-1

現在令T(0)=T(1)=b,b為一常數(因為不必排序),接著按上式可算得T(2) = 2b + 2c。現在假設:

T(i) <= k*i*ln(i), for i=2∼n-1, k=2b+2c

其中ln為自然對數。若在前述i=2∼n-1的假設之下,仍能證明i=n的假設符合,亦即T(n) <= k*n*ln(n),那麼這項假設即可證明是對的(此即為歸納證明法)。首先看一下初始狀況:

T(2) = 2b + 2c <= (2b+2c)*2*ln(2) = (2b+2c)*1.38

故初始狀況是符合前述假設的。現在開始考慮n個資料時的情況:

T(n) <= 2 Σ(k*i*ln(i)) / n + 4b/n + cn, i=2∼n-1

其中4b/n即是i=0∼1時抽離Σ出來的值。由於k是常數,可調到Σ外面,全式成為:

T(n) <= 2k Σ(i*ln(i)) / n + 4b/n + cn, i=2∼n-1

現在考慮Σ(i*ln(i))一式,由於是離散加總,必小於等於Upper Bound的連續積分,故:

Σ(i*ln(i)), i=2∼n-1 <= ∫x*ln(x)dx, x=2∼n

從積分公式可查得:

∫x^m*ln(x)dx = x^(m+1) * (ln(x)/(m+1) - 1/(m+1)^2)

因此:

∫x*ln(x)dx = n^2 (ln(n)/2 - 1/4)


代入前式,可得:

T(n) <= k*n*ln(n) - k*n/2 + 4b/n + cn

若4b/n + cn - k*n/2 <= 0,那麼T(n) <= k*n*ln(n)就成立了。亦即:

k >= 2c + 8b/n^2

由於前述假設n>=2,故n^2 >= 4,因此上式成立,可證明T(n) <= k*n*ln(n)。由於ln(n) = log(n)/log(e),而log(e)為一常數,故:

T(n) <= a*n*log(n), a為一常數

可證得其平均情況複雜度為O(nlogn)。
作者 : yihcheng(yihcheng)
[ 貼文 137 | 人氣 2 | 評價 770 | 評價/貼文 5.62 | 送出評價 0 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2009/6/30 上午 03:52:40
好利害,你已經把演算法前面一半的內容介紹完了.
不知何時會有後面一半 network flow, np-complete, p-space, tree decomposition, approximation 的內容呢 :p
 板主 : Jammy , simula
 > 一般討論區 - 討論區
 - 最近熱門問答精華集
 - 全部歷史問答精華集
 - 一般討論區 - 知識庫
  ■ 全站最新Post列表
  ■ 我的文章收藏
  ■ 我最愛的作者
  ■ 全站文章收藏排行榜
  ■ 全站最愛作者排行榜
  ■  月熱門主題
  ■  季熱門主題
  ■  熱門主題Top 20
  ■  本區Post排行榜
  ■  本區評價排行榜
  ■  全站專家名人榜
  ■  全站Post排行榜
  ■  全站評價排行榜
  ■  全站人氣排行榜
 請輸入關鍵字 
  開始搜尋
 
Top 10
評價排行
一般討論區
1 青衫 5370 
2 HKLN.net 1370 
3 冼鏡光 650 
4 simula 610 
5 joe 560 
6 DEMO999 520 
7 小朱 490 
8 jonay 480 
9 BlueTulip 460 
10 Jammy 370 
一般討論區
  專家等級 評價  
  一代宗師 10000  
  曠世奇才 5000  
  頂尖高手 3000  
  卓越專家 1500  
  優秀好手 750  
Microsoft Internet Explorer 6.0. Screen 1024x768 pixel. High Color (16 bit).
2000-2019 程式設計俱樂部 http://www.programmer-club.com.tw/
0.125