《數(shù)據(jù)結(jié)構(gòu)與算法》第2章 算法的基本概念與算法分析

第2章算法的基本概念與算法分析

2.1算法的基本概念

2.2算法的評估2.3算法的復(fù)雜性度量2.1.1一個簡單的算法問題 把攝氏溫度值轉(zhuǎn)換為華氏溫度值。 已知計算公式為：F=(9/5)C+32，其計算過程可描述如下：輸入一個攝氏溫度值C；C乘以常數(shù)9/5=1.8；乘積與常數(shù)32相加；輸出相加的結(jié)果F。 這就是求解該問題的算法，不過，計算機“看”不懂這個算法，需要用程序設(shè)計語言描述：

#include＜iostream.h＞

voidmain（）

{

floatC,F；

constfloatfac=1.8，inc=32.0；

cout<<"EnterCelsiustemperature："；

cin>>C； ∥輸入攝氏溫度值

F=C；

F=C

fac；

F=F+inc;

cout<<endl<<"TheFahrenheittemperatureis："；

cout<<F<<"F(=“<<C<<"C)＼n"；

｝

例如輸入40.2，計算結(jié)果將在屏幕上顯示：

EnterCelsiustemperature：40.2

TheFahrenheittemperatureis：104.36F(=40.2C)2.1.2什么是算法算法1.Webster辭典定義：算法即在有限步驟內(nèi)解一個數(shù)學(xué)問題的過程，步驟中常常包括某一操作的重復(fù)。更廣義地說，一個算法就是為解一個問題或?qū)崿F(xiàn)某一目標(biāo)的逐步過程。2.D.E.Knuth定義：一個算法，就是一個有窮規(guī)則的集合，其中之規(guī)則規(guī)定了一個解決某一特定類型的問題的運算序列；此外，它還應(yīng)有五個重要特性：有窮性：一個算法必須總是在執(zhí)行有窮步之后結(jié)束；確定性：算法的每一步驟，必須是確切地定義的；輸入：有0或多個輸入值；輸出：有1或多個輸出值；能行性：算法中要做的運算都是相當(dāng)基本的，能夠精確地進行的。3.形式化定義：算法就是一個對任一有效輸入能夠停機的Turing機。2.1.3算法與問題如同生物學(xué)家把自然界的所有生物作為自己的研究對象，計算（Computation）學(xué)科或稱計算機科學(xué)則把問題作為自己的研究對象。用計算機來解決問題（Problemsolving）稱為問題求解。算法要解決的是一類問題，算法的執(zhí)行則針對的是問題的實例。每一個問題都可以看作是該問題的所有實例（instance）的集合。一個問題的一個實例就是為計算該問題所需的一組輸入。例：整數(shù)乘法問題 全部可能輸入集合：{<a,b>|a,b∈Z}，其中Z表示整數(shù)集；一個實例：<2,4>,求：2×4=?旅行商問題(TravelingSalesmanProblem)

實例集為：{n,Wn*n=[Wij]|n∈Z,Wij∈R,i,j∈[1,…,n]}； 一個實例：n=4,該實例（n,W）就是求環(huán)游4個城市(1,2,3,4)且代價和最小的周游路線，其中權(quán)矩陣W給出了4個城市之間的距離（代價），Wij表示由城市i到城市j的距離（代價）。語言L<G,Σ>的識別問題 其中G為文法，Σ為一字符集。L(G)為Σ上由G生成的語言，L(G)∈Σ*，Σ*表示由Σ中的字符組成的所有字符串集合。 語言L的識別問題{G,Σ,ω|ω∈Σ*}的一個實例ω∈Σ*，識別算法判斷ω∈L(G)是否成立。 一般對于問題P，總有其相應(yīng)的實例集I，那么，一個算法A是問題P的算法，意味著把P的任一實例input∈I作為A的輸入，都能得到問題P的正確的輸出。一個問題可以有許多個不同的算法。2.1.4算法與程序程序(Program)可以用來描述算法，同一個算法可以用不同的語言編寫的程序來描述。程序不一定是算法。程序設(shè)計可以分為四個層次：算法、方法學(xué)、語言和工具。抽象級更新速度算法程序設(shè)計方法程序設(shè)計語言編程工具2.2.1算法的正確性算法的正確性是評估的前提。有些算法，特別是一些十分精致巧妙的算法，其正確性需要證明，有的證明難度較大，例如無向圖單源最短路徑問題的Dijkstra算法，構(gòu)造最優(yōu)二分搜索樹的動態(tài)規(guī)劃算法的Knuth改進。有些算法，其正確性是明顯的， 例如選擇排序算法。2.2.2時間代價評估算法的時間代價是算法分析的核心。算法的時間代價的大小用算法的時間復(fù)雜度(TimeComplexity)來度量。但要考慮到以下因素： 用來運行算法的計算機的性能的差別；算法運行的軟件平臺和描述語言的差別；算法所解的問題是多種多樣的；同一問題的算法對不同的實例，所花的時間開銷也可能有很大的差別。2.2.3空間代價空間消耗是衡量算法優(yōu)劣的另一重要因素。算法的空間代價的大小用算法的空間復(fù)雜度（SpaceComplexity）來度量。不過算法的空間復(fù)雜性分析的重要性常常列于時間復(fù)雜性分析之后。在許多應(yīng)用問題中，人們往往以適當(dāng)增加算法的空間代價來減少時間代價?？臻g復(fù)雜度的分析類似于時間復(fù)雜度的分析，其有關(guān)的概念和方法幾乎是平行的。

2.2.4最優(yōu)性一個算法不一定是最優(yōu)的。所謂最優(yōu)算法是指在某一種度量標(biāo)準(zhǔn)之下，優(yōu)于該問題的所有（可能的）算法。一般，某一問題的最優(yōu)算法是指在時間復(fù)雜度的計算基礎(chǔ)上的最優(yōu)性。

例：求n個不同整數(shù)中的最大元MaxElement

對于任何n個整數(shù)，要求其最大元，至少需進行n-1次比較，因此，可以說上述算法Max(S)是最優(yōu)的。為了證明在n個不同元中求出最大元，至少需n-1次比較，可以把n個元劃分為三個動態(tài)的組A,B,C：A：未知元的集合B：已肯定不是最大元的元素集合C：最大元的集合。不難證明，任何一個通過二元比較求最大元的算法都是要從三個集合的元數(shù)為(n,0,0)（即|A|=n,|B|=0,|C|=0）狀態(tài)開始，經(jīng)過運行，最終達(dá)到(0,n-1,1)狀態(tài)，即：這實際上是元素從集合A向B和C中移動的過程。但每次兩個元的比較至多只可把一個較小的元素從集合A移至集合B。因此，任何最大元算法至少要進行n-1次比較，從而證明了上述最大元算法Max(A)是最優(yōu)的。2.3.1算法復(fù)雜性度量的基本操作算法的時間代價的度量不應(yīng)依賴于算法運行的硬件和軟件平臺，因此不能從下面幾個方面來度量時間代價：

算法運行的實際執(zhí)行時間；運行過程中所執(zhí)行的指令條數(shù)；運行過程中程序循環(huán)的次數(shù)。 因此需要引入基本操作的概念來度量時間代價。 基本操作就是指算法運行中起主要作用且花費最多時間的操作。例如：兩個實數(shù)矩陣的乘法問題中，矩陣的實數(shù)元素之間的數(shù)乘是基本操作；對N個整數(shù)進行排序的算法中，整數(shù)間的比較是基本操作。問題實例長度算法運行的時間（或空間）代價還與問題實例長度，即輸入規(guī)模有關(guān)，這稱為問題實例長度。

問題實例長度是指作為該問題的一個實例的輸入規(guī)模大小。例如：

排序問題：問題實例長度是待排序元素序列的長度n；

矩陣乘積：問題實例長度是矩陣（指n階方陣）的階數(shù)n；

圖的最短路徑問題：圖G=<V,E>的頂點數(shù)n=||V||和邊數(shù)m=||E||是問題實例長度；

字符串匹配問題：文本T的長度n，亦可再加上樣本P的長度m為問題實例長度。2.3.2問題實例長度算法的時間（或空間）代價由該算法用于問題長度為n的實例所需要的基本操作次數(shù)來刻畫。一般一個算法的時間復(fù)雜度用函數(shù)T(n)

或T(n,m)

表示，空間復(fù)雜度用S(n)表示。算法的比較是根據(jù)復(fù)雜度函數(shù)的漸進性質(zhì)的比較進行的。 例如：算法A和算法B，其時間復(fù)雜度函數(shù)為TA(n)和TB(n)，在圖2.1中，雖然當(dāng)n<n0時TB(n)<TA(n)，但在n>n0時，或說n充分大時(n→∞)，有TA(n)<TB(n)，因此認(rèn)為算法A優(yōu)于算法B。2.3.3復(fù)雜度函數(shù)及其漸進性質(zhì)圖2.1算法的漸進性質(zhì)

例：插入排序算法Insertsort

n=10時，有三種輸入： 正序：123456789109次比較 逆序：1098765432145次比較 隨機：3745102961828次比較 同一算法，相同的問題長度，不同的輸入，其時間代價一般不同。因此在實際的算法分析中，復(fù)雜度函數(shù)值T(n)不是唯一的，在大多數(shù)情況下取其最大值，即最壞情形的時間（空間）復(fù)雜度。2.3.4最壞情形和最好情形 設(shè)Dn為問題P的所有長度為n的實例集合，輸入實例I∈Dn

，||I||=n，而t(I)為用來解問題P的算法A在以I為輸入時的執(zhí)行代價（基本操作次數(shù)），則

W(n)稱為算法A的最壞情形(WorstCase)時間復(fù)雜度。類似的，還可以定義最好情形（BestCase）時間復(fù)雜度：

2.3.5平均情形和算法的期望復(fù)雜度在許多實際問題中，使算法A耗費最大代價W(n)的實例往往只占很小的一部分，而大多數(shù)實例耗費的代價常常遠(yuǎn)小于W(n)，用W(n)來表示算法的代價一般比實際的開銷大很多。因此，評價算法性能的更好的方法是用期望復(fù)雜度(ExpectedComplexity)，或稱平均情形

(AverageCase)復(fù)雜度。

設(shè)算法A的輸入為I∈Dn的概率為P(I)，則

其中P(I)滿足為實例輸入I出現(xiàn)的概率，t(I)為算法A完成實例I的耗費值（即基本操作次數(shù)）。期望復(fù)雜度比最壞情形復(fù)雜度更好的刻畫了算法的性能，但是，由于Dn一般很大，P(I)和t(I)較難計算，因此，平均情形的復(fù)雜度分析比較難。例如：在數(shù)組L[1,…,n]中搜索，求使L[j]=X的位置j。

順序搜索算法SeqSearch

因為L[1,…,n]長度為n，不同的輸入實例由X的值決定，實例集Dn由下列實例組成： （1）X在L中，共有n種情況：I1,…,In，Ii表示X=L[i] (i=1,…,n)； （2）X不在L中，這時X有許多可能值，把它們統(tǒng)記為 In+1。因為當(dāng)X=L[k]時，t(Ik)=k，(k=1,…,n)，X不在L中時，t(In+1)=n。這時W(n)容易計算：

W(n)=MAX{t(Ik)|k=1,2,…,n,n+1}=n。 但計算A(n)則應(yīng)首先設(shè)定I在Dn中的分布： 設(shè)X在L中的概率為q，故X不在L中的概率為1-q，假定X在L中，它等于L的n個元素是等可能的，即P(Ik)=Pk=q/n,(k=1,…,n),P(In+1)=Pn+1=1-q，

當(dāng)q=1，即已知X在L中，A(n)=(n+1)/2，q=1/2，即X有一半可能在L中，A(n)=3n/4+1/4。也就是說，在上面的假設(shè)條件下，我們的順序搜索的平均代價大約是n/2次比較和3n/4次比較。 各種復(fù)雜度函數(shù)的表示方法大致可按表達(dá)的精確程度分為下面的三個等級：解析表達(dá)式 用解析表達(dá)式刻畫復(fù)雜度函數(shù)是最精確的表達(dá)方式。例如求n元中之最大元算法MaxElement的復(fù)雜度為T(n)=W(n)=A(n)=n–1。 順序搜索算法的最壞情形時間復(fù)雜度為W(n)=n；在指定分布條件及q=1情形下的期望時間復(fù)雜度為A(n)=(n+1)/2。2.3.6復(fù)雜度函數(shù)的表示階（Order）表達(dá)式 對于算法的復(fù)雜度的研究主要是側(cè)重在其漸進性質(zhì)，即當(dāng)問題長度n比較大的情形。為了簡化算法復(fù)雜度分析的方法，往往只需計算當(dāng)問題規(guī)模較大時算法的漸進復(fù)雜度的階。定義1.1

稱（復(fù)雜度）函數(shù)T(n)是O(f(n))的，即T(n)=O(f(n))，如果存在常數(shù)c>0與n0

，當(dāng)n>n0

時有T(n)≤cf(n)。例如：T1(n)=(n+1)/2=O(n), T2(n)=3n2+4n+5=O(n2)定義1.2

稱（復(fù)雜度）函數(shù)T(n)是Ω(f(n))的，即T(n)=Ω(f(n))，如果存在常數(shù)c>0與n0

，當(dāng)n>n0時有T(n)≥cf(n)。

例如：T1(n)=(n+1)/2=Ω(n),

T2(n)=3n2+4n+5=Ω(n2)定義1.3

稱（復(fù)雜度）函數(shù)T(n)是θ(f(n))的，即T(n)=θ(f(n))，如果存在常數(shù)c1,c2>0與n0

，當(dāng)n>n0

時有c1f(n)≥T(n)≥c2f(n)。 例如：T1(n)=(n+1)/2=θ(n),

T2(n)=3n2+4n+5=θ(n2)

顯然，如果T(n)=O(f(n))且T(n)=Ω(f(n))，則T(n)=θ(f(n))。2.4算法設(shè)計與分析的重要性摩爾(Moore)定律：計算機處理器的運算速度每十八個月要翻一番。但是，電子計算機的運算速度肯定是有上限的，它不可能一直“翻”下去，即使計算機的速度不斷提高，算法研究仍然是必要的。無論硬件性能如何提高，算法研究仍然是推動計算機技術(shù)發(fā)展的關(guān)鍵。

2.4.1一個實例 插入排序算法和歸并排序算法中，后者較優(yōu)。 對n(=1000000)個數(shù)據(jù)進行排序。 在一臺高速的計算機A（每秒鐘處理109條指令）上，采用插入排序算法。 在一臺較慢的計算機B（每秒鐘處理107條指令）上，采用歸并排序算法。 在計算機A上運行插入排序算法，對n項數(shù)據(jù)排序，需要執(zhí)行2n2條指令，共需時間為：(2*(106)2)/109＝2000(sec)

在計算機B上運行歸并排序算法，對n項數(shù)據(jù)排序，需要執(zhí)行50nlogn條指令，共需時間為：(50*106*log106)≈100(sec)2.4.2計算機應(yīng)用領(lǐng)域的變化在了解計算機性能不斷提高的同時，必須看到，人類使用計算機解決的應(yīng)用問題也在不斷變化：應(yīng)用的范圍不斷擴張；應(yīng)用問題的規(guī)模不斷增加；應(yīng)用問題本身也越來越復(fù)雜。 計算機技術(shù)的進步離不開算法研究，如多媒體技術(shù)中的數(shù)據(jù)壓縮算法的研究，計算機安全中數(shù)據(jù)加密算法的研究。許多組合優(yōu)化，也只能靠算法的研究來解決，例如：旅行商(TravelSalesman)難解問題 假定計算機每秒可處理1000000次浮點運算，采用一般TSP算法解n=10（十個城市）的情形約需0.18秒；但當(dāng)城市數(shù)n=20，同一機器上運行需要1929年！試想，這時改用速度提高100倍的計算機，可以縮短為19年，這仍然是不可接受的。2.4.3 計算機技術(shù)的發(fā)展需要設(shè)計有效算法

0-1背包(0-1Knapsack)問題

n=10需1ms，n=60需要366世紀(jì)！這時計算機提高速度10000倍，仍要3.66年。

算法與計算復(fù)雜性理論的研究表明，當(dāng)問題的復(fù)雜度較高時單純靠提高計算機性能是不能解決問題的。 設(shè)五種復(fù)雜度函數(shù)分別為n，n2，n5，2n，3n，采用速度為每秒鐘處理1000000次基本操作的PC機，其處理問題長度分別為n=10，30，60的實例的時間代價如下表：

表2.1時間代價需求表表2.2機器速度提高對解題能力的影響2.5.1MAXMIN問題的平凡算法

步驟：①:求n元中的最小元；②:求余下的n–1個元中的最大元。

例：求最大最小元的平凡算法MAXMIN1

算法是正確的以元素之間的比較為基本操作，則①的代價為n–1，②的代價為n–2，故總時間代價為2n–3。故T(n)=W(n)=A(n)=2n–3，亦可記為T(n)=O(n)或T(n)=θ(n)。空間代價除了數(shù)組L之外，只需幾個工作單元，一般記為S(n)=O(1)。算法的最優(yōu)性討論：從n元中求最小元用n-1次比較，從n–1元中求最大元用n–2次比較都是最優(yōu)的。但把二者合起來用2n–3次比較求最大、最小元并不一定最優(yōu)。求MIN與MAX時它們是相關(guān)的，例如L[i]>L[j]指出L[i]不可能是最小元，L[j]不可能是最大元，因此算法MAXMIN1應(yīng)可改進。2.5.2第一次改進把求MAX和MIN放在一起處理：

例：求最大最小元的改進算法MAXMIN2

此算法需2n–2次比較，即T(n)=W(n)=A(n)=

2n–2。沒有改進，但可發(fā)現(xiàn)循環(huán)體中的不合理處：如果(MAX<L[i])為真，則(MIN>L[i])為假，故有改進算法II。2.5.3第二個改進算法例：求最大最小元的改進算法MAXMIN3

最好情形B(n)=n–1，最壞情形W(n)=2n–2，平均情形時間復(fù)雜度A(n)應(yīng)介于二者之間，估計A(n)<2n–3。2.5.4采用淘汰賽策略的改進算法“淘汰賽算法”

MAXMIN：step1.對n個元兩兩比較，共用n/2

次比較；step2.對“勝者組”（即step1比較中的較大元，及當(dāng)n為奇數(shù)時未參加比較的元）共n/2個元素求最大元，共用n/2-1次比較；step3.對“敗者組”（即step1比較中的較小元，及n為奇數(shù)時未參加比較的元）共

n/2個元素求最小元，共用n/2-1次比較； 在step1、step2分別求出的最大元、最小元即所求。不難證明，無論n為奇偶，都有：算法MAXMIN是假定n=2k條件下設(shè)計的，對于一般的正整數(shù)n時間復(fù)雜度應(yīng)為T(n)=W(n)=A(n)=3n/2-2。算法MAXMIN的設(shè)計包含一定的設(shè)計技巧，有時采用設(shè)計有效算法的一些常用設(shè)計技術(shù)（將在第九章介紹）也可以收到改進算法復(fù)雜度的效果。例如，我們可以采用分治策略，按照分治策略，把L[1,…,n]劃分為兩部分L1、L2，用同一算法對L1、L2分別求最大最小元，兩個最大元中較大者和兩個最小元中較小者即所求。MAXMIN問題的分治算法同樣可以把算法復(fù)雜度降至大約1.5n。2.5.5算法MAXMIN的討論算法MAXMIN的時間復(fù)雜度是不可改進的，因此它是一個最優(yōu)算法。MAXMIN問題的分治算法是一個遞歸算法。在遞歸算法進行復(fù)雜度分析時，一般要遇到解遞歸方程或遞歸不等式。 這里僅對一類最常見的遞歸方程進行討論： 其中：整數(shù)a≥1，b>1，c≥0，T(n)，d(n)為非負(fù)（整）函數(shù)。利用下面的結(jié)果，可以對不同情形分別判斷函數(shù)T(n)的階。主項定理1

對于上面的遞歸方程（2.1），有(a)如果，若a>1則 ；若a=1則；(b)如果，若a<b則；若a=b則；若a>b則；利用主項定理1對算法MAXMIN進行分析，T(n)=2T(n/2)+2可以立即得到：

這與T(n)=3n/2-2一致。下面的主項定理2一般被稱為主項定理（Mastertheorem），與主項定理1的依據(jù)實際是相同的，不過，其結(jié)果比主項定理1更強。主項定理2（Mastertheorem）對于遞歸方程(2.1)，有(1)如果對某常數(shù)ε>0成立，

則；(2)如果，則；(3)如果對某常數(shù)ε>0成立，且存在常數(shù)e<1使得對所有充分大的n，有，則。 END求n個不同整數(shù)中的最大元MaxElementtemplate<classType>intMax(TypeS[],intn){

Typemax=S[0];

inti=1;

while(i<n){

if(max<S[i])max=S[i];i++;}returnmax;}返回選擇排序算法template<classType>

voidSelectionSort(TypeA[],intn){

for(inti=1;i<=n-1;i++){

intmin=i;

for(intj=i+1;j<=n;j++)

if(A[j]<A[min])min=j;

Swap(A[i],A[min]);

}

return;

}返回插入排序算法InsertSort

template<classType>void

InsertSort(TypeA[],intn){for(inti=2;i<=n;i++){TypeV=A[i];

intj=i-1;

while((A[j]>V)&&(j>0)){A[j+1]=A[j];j=j–1;}A[j+1]=V;

return;}返回順序搜索算法SeqSearch

template<classType>

intSearch(TypeL[],TypeX,intn){

intj=1;while((j<=n)&&(L[j]!=X))j++;

returnj;}返回求最大最小元的平凡算法MAXMIN1template<classType>#inclu