[计算机]演算法简介

《[计算机]演算法简介》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二十章演算法簡介知己知彼，百戰不貽－孫子1演算法簡介內容前言20.1演算法分析20.2個別擊破策略20.3貪婪策略20.4動態規劃20.5刪除與搜尋策略20.6課後習題20.7欲罷不能2演算法簡介前言演算法(Algorithm)電腦上解決問題的方法包括明確的輸出入資料和詳細且有限的執行步驟了解每個演算法在不同狀況下所花的時間，而從中挑選適合的演算法以迅速得到答案演算法設計策略3演算法簡介20.1演算法分析在電腦上解決問題的基本架構演算法以程式描述後在電腦上執行，資料輸入至程式後，經過程式對資料的運算，最後產生解答資料演算法（程式）圖20.1解答4演算法簡介時間複雜度(TimeComplex

2、ity)假設演算法A能解問題P問題P的輸入資料量為N假設資料量為N的資料樣本(DataInstance)有D1,D2,...,Di,...,Dm共m種令T(Di)表示當輸入資料為Di時演算法A要執行的運算或步驟的總次數演算法A的最好狀況時間複雜度(Best-CaseTimeComplexity)T(Di)(1im)中最小的值，即min1im{T(Di)}5演算法簡介時間複雜度(cont.)演算法A的最差狀況時間複雜度(Worst-CaseTimeComplexity)T(Di)(1im)中最大者，即max1im{T(Di)}演算法A的一般狀況時間複雜度(Average-Cas

3、eTimeComplexity)T(Di)(1im)的平均值或期望值(在某機率假設下)說“演算法A的時間複雜度為C”就是指其最差狀況時間複雜度為C6演算法簡介時間複雜度(cont.)範例若問題P之輸入資料量為N的樣本有D1,D2,D3三種，且T(D1)=3,T(D2)=N,T(D3)=N3演算法A的最好狀況時間複雜度為3演算法A的最差狀況為N3演算法A的一般狀況為(3+N+N3)/3稱演算法A的時間複雜度為N37演算法簡介漸近上限(AsymptoticUpperBound)O階次如果存在某固定正實數c及某個非負整數m使得對所有的nm，不等式g(n)cf(n)都成立，則g(n)=O(

4、f(n))，稱f(n)為g(n)的漸近上限Example:N2+10N=O(N2)，因為當n10時，N2+10N2N2稱N2為N2+10N的漸進上限8演算法簡介漸近下限(AsymptoticLowerBound)階次若存在某固定正變數c及某非負整數m使得對所有nm，不等式g(n)cf(n)都成立，則g(n)=(f(n))，稱f(n)為g(n)的漸近下限Examplen3=(n2)，因為當n1時，n31n2，所以n2為n3的漸近下限。9演算法簡介真正階次(ExactOrder)若存在某固定正變數c及某非負整數m使得對所有nm，不等式g(n)cf(n)都成立，則g(n)=(

5、f(n))，稱f(n)為g(n)的漸近下限ExampleN2+10N=(N2)，因為N2+10N=O(N2)且N2+10N=(N2)。10演算法簡介真正階次(cont.)當n足夠大時，2n>n3>n2>nlogn>n>logn11演算法簡介指數函數分析指數函數(ExponentialFunction)例如：f(n)=cp(n)，其中c為常數，p(n)為n的多項式函數(PolynomialFunction)(如n，n2+10，log2n，nlog2n)Example:2n、3n、4logn等函數函數值上升速度相當快時間複雜度為指數函數階次的演算法在資料量足夠多時需要相當長的時間才能解得答案

6、12演算法簡介多項式時間演算法(Polynomial-TimeAlgorithm)時間複雜度是O(p(n))的演算法，其中p(n)為n的多項式函數電腦上可解（Tractable）的問題能用多項式時間演算法解得答案的問題，即能用電腦在合理時間內求得答案例如：排序及搜尋等問題13演算法簡介排序法及搜尋法的時間複雜度時間複雜度演算法最好狀況最差狀況插入排序O(n)O(n2)氣泡排序O(n)O(n2)謝耳排序O(n)O(n2)兩兩合併排序O(n)O(nlog2n)循序搜尋O(1)O(n)二分搜尋O(1)O(log2n)14演算法簡介最佳演算法(OptimalAlgorithm)若可解問題P的演算法

7、A的時間複雜度為t，而解問題P的演算法最少需要t時間，則稱演算法A是解問題P的最佳演算法例如：兩兩合併排序法是最佳排序演算法排序n個數的問題最少需要O(nlog2n)時間兩兩合併排序法的時間複雜度是O(nlog2n)15演算法簡介難解問題(IntractableProblem)若問題P無法以多項式時間演算法解得答案，則問題P無法於電腦上在合理時間內求得答案，稱問題P為難解問題，或NP-Complete問題Ex