《算法設(shè)計(jì)與分析-C++語(yǔ)言描述（第4版）》全套教學(xué)課件

算法設(shè)計(jì)與分析

——C++語(yǔ)言描述DeSignandAnalysisofAlgorithmsInC++

全套可編輯PPT課件

課程簡(jiǎn)介課程名稱：算法設(shè)計(jì)與分析

DesignandAnalysisofAlgorithms先修課程：面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言C++，數(shù)據(jù)結(jié)構(gòu)

第1部分算法和算法分析

第1章算法問(wèn)題求解基礎(chǔ)

1.1算法概述1.2問(wèn)題求解方法

1.3算法設(shè)計(jì)與分析

1.4遞歸和歸納

1.1算法概述

1.1.1什么是算法

算法（algorithm）一個(gè)算法是對(duì)特定問(wèn)題求解步驟的一種描述，它是指令的有限序列。此外，算法具有下列5個(gè)特征:

輸入（input）：算法有零個(gè)或多個(gè)輸入量；輸出（output）：算法至少產(chǎn)生一個(gè)輸出量；確定性（definiteness）：算法的每一條指令都有確切的定義，沒(méi)有二義性；能行性（effectiveness）：算法的每一條指令必須足夠基本，它們可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)；有窮性（finiteness）：算法必須總能在執(zhí)行有限步之后終止。

歐幾里德算法(輾轉(zhuǎn)相除法)計(jì)算兩個(gè)整數(shù)m和n（0≤m＜n)的最大公約數(shù)，記為gcd(m,n)。

【程序1-1】

歐幾里德遞歸算法intRGcd(intm,intn){if(m==0)returnn;returnRGcd(n%m,m);}intGcd(intm,intn){if(m>n)Swap(m,n);returnRGcd(m,n);}

【程序1-1】

歐幾里德遞歸算法intRGcd(intm,intn){if(m==0)returnn;returnRGcd(n%m,m);}intGcd(intm,intn){if(m>n)Swap(m,n);returnRGcd(m,n);}

【程序1-2】

歐幾里德迭代算法intGcd(intm,intn){ if(m==0)returnn;if(n==0)returnm; if(m>n)Swap(m,n); while(m>0){ intc=n%m;n=m;m=c; } returnn;}

【程序1-3】Gcd的連續(xù)整數(shù)檢測(cè)算法intGcd(intm,intn){ if(m==0)returnn;if(n==0)returnm; intt=m>n?n:m; while(m%t||n%t)t--; returnt;}1.1.2為什么學(xué)習(xí)算法

算法是計(jì)算機(jī)科學(xué)的基礎(chǔ)，更是程序的基石，只有具有良好的算法基礎(chǔ)才能成為訓(xùn)練有素的軟件人才。對(duì)于計(jì)算機(jī)專業(yè)的學(xué)生來(lái)說(shuō)，學(xué)習(xí)算法的理由是非常充分的。因?yàn)槟惚仨氈纴?lái)自不同計(jì)算領(lǐng)域的重要算法，你也必須學(xué)會(huì)設(shè)計(jì)新的算法、確認(rèn)其正確性并分析其效率。隨著計(jì)算機(jī)應(yīng)用的日益普及，各個(gè)應(yīng)用領(lǐng)域的研究和技術(shù)人員都在使用計(jì)算機(jī)求解他們各自專業(yè)領(lǐng)域的問(wèn)題，他們需要設(shè)計(jì)算法，編寫(xiě)程序，開(kāi)發(fā)應(yīng)用軟件，所以學(xué)習(xí)算法對(duì)于越來(lái)越多的人來(lái)說(shuō)變得十分必要。

1.2問(wèn)題求解方法

1.2.1問(wèn)題和問(wèn)題求解問(wèn)題求解（problemsolving）是尋找一種方法來(lái)實(shí)現(xiàn)目標(biāo)。問(wèn)題求解過(guò)程（problemsolvingprocess）是人們通過(guò)使用問(wèn)題領(lǐng)域知識(shí)來(lái)理解和定義問(wèn)題，并憑借自身的經(jīng)驗(yàn)和知識(shí)去選擇和使用適當(dāng)?shù)膯?wèn)題求解策略、技術(shù)和工具，將一個(gè)問(wèn)題描述轉(zhuǎn)換成問(wèn)題解的過(guò)程。計(jì)算機(jī)求解問(wèn)題的關(guān)鍵之一是尋找一種問(wèn)題求解策略（problemsolvingstrategy），得到求解問(wèn)題的算法，從而得到問(wèn)題的解。

1.2.2問(wèn)題求解過(guò)程

理解問(wèn)題（understandtheproblem）

設(shè)計(jì)方案（deviseaplan）

實(shí)現(xiàn)方案（carryouttheplan）

回顧復(fù)查（lookback）

1.2.3系統(tǒng)生命周期

一個(gè)計(jì)算機(jī)程序的開(kāi)發(fā)過(guò)程就是使用計(jì)算機(jī)求解問(wèn)題的過(guò)程。軟件工程（softwareengineering）將軟件開(kāi)發(fā)和維護(hù)過(guò)程分成若干階段，稱為系統(tǒng)生命周期（systemlifecycle）或軟件生命周期。

軟件生命周期劃分為:分析（analysis）設(shè)計(jì)（design）編碼（codingorprogramming）測(cè)試（testing）維護(hù)（maintenance）等5個(gè)階段。前4個(gè)階段屬于開(kāi)發(fā)期，最后一個(gè)階段處于運(yùn)行期。

1.3算法設(shè)計(jì)與分析

1.3.1算法問(wèn)題求解過(guò)程

算法分類(lèi)一個(gè)精確算法（exactalgorithm）總能保證求得問(wèn)題的解。一個(gè)啟發(fā)式算法（heuristicalgorithm）通過(guò)使用某種規(guī)則、簡(jiǎn)化或智能猜測(cè)來(lái)減少問(wèn)題求解時(shí)間。

對(duì)于最優(yōu)化問(wèn)題，一個(gè)算法如果致力于尋找近似解而不是最優(yōu)解，被稱為近似算法（approximationalgorithm）。如果在算法中需做出某些隨機(jī)選擇，則稱為隨機(jī)算法（randomizedalgorithm）。1.3.2如何設(shè)計(jì)算法

使用計(jì)算機(jī)的問(wèn)題求解策略主要指算法設(shè)計(jì)策略（algorithmdesignstrategy）。

1.3.3如何表示算法

算法描述方法自然語(yǔ)言流程圖偽代碼程序設(shè)計(jì)語(yǔ)言本書(shū)使用C/C++語(yǔ)言描述算法

1.3.4如何確認(rèn)算法確認(rèn)一個(gè)算法是否正確的活動(dòng)稱為算法確認(rèn)（algorithmvalidation）使用數(shù)學(xué)方法證明算法的正確性，稱為算法證明（algorithmproof）。程序測(cè)試（programtesting）是指對(duì)程序模塊或程序總體，輸入事先準(zhǔn)備好的樣本數(shù)據(jù)（稱為測(cè)試用例，testcase），檢查該程序的輸出，來(lái)發(fā)現(xiàn)程序存在的錯(cuò)誤及判定程序是否滿足其設(shè)計(jì)要求的一項(xiàng)積極活動(dòng)。

1.3.5如何分析算法算法分析（algorithmanalysis）活動(dòng)是指對(duì)算法的執(zhí)行時(shí)間和所需空間的估算。當(dāng)然在算法寫(xiě)成程序后，便可使用樣本數(shù)據(jù)，實(shí)際測(cè)量一個(gè)程序所消耗的時(shí)間和空間，這稱為程序的性能測(cè)量（performancemeasurement）。

1.4遞歸和歸納

1.4.1遞歸

遞歸定義遞歸（recursive）定義是一種直接或間接引用自身的定義方法。一個(gè)合法的遞歸定義包括兩部分：基礎(chǔ)情況（basecase）和遞歸部分。例1-1

斐波那契數(shù)列

例1-1

斐波那契數(shù)列

遞歸算法當(dāng)一個(gè)算法采用遞歸方式定義時(shí)便成為遞歸算法。一個(gè)遞歸算法是指直接或間接調(diào)用自身的算法。

【程序1-4】

求FnlongFib(longn){ if(n<=1)returnn; elsereturnFib(n-2)+Fib(n-1);}

可以用所謂的遞歸樹(shù)（recursivetree）來(lái)描述程序1-4的函數(shù)Fib執(zhí)行時(shí)的調(diào)用關(guān)系。

圖1-2計(jì)算Fib（4）的遞歸樹(shù)

遞歸數(shù)據(jù)結(jié)構(gòu)使用遞歸方式定義的數(shù)據(jù)結(jié)構(gòu)稱為遞歸數(shù)據(jù)結(jié)構(gòu)（recursivedatastructure）。

1.4.2遞歸算法示例

例1-2

逆序輸出正整數(shù)的各位數(shù)

【程序1-5】

voidPrintDigit(unsignedintn){ cout<<n%10; //輸出最后一位數(shù)dk if(n>=10)PrintDigit(n/10); //以逆序輸出前k-1位數(shù)}

例1-3漢諾塔問(wèn)題（towerofHanoi）假定有三個(gè)塔座：X，Y，Z，在塔座X上有n個(gè)直徑大小各不相同，按圓盤(pán)大小從小到大編號(hào)為1，2，…，n的圓盤(pán)。現(xiàn)要求將X塔座上n個(gè)圓盤(pán)移到塔座Y上，并仍按同樣順序疊排。圓盤(pán)移動(dòng)時(shí)必須遵循下列規(guī)則：（1）每次只能移動(dòng)一個(gè)圓盤(pán)；（2）圓盤(pán)可以加到塔座X，Y，Z中任意一個(gè)上；（3）任何時(shí)刻都不能將一個(gè)較大的圓盤(pán)放在較小的圓盤(pán)之上。

【程序1-6】

漢諾塔問(wèn)題enumtower{A='X',B='Y',C='Z'};voidMove(intn,towerx,towery){//將第n個(gè)圓盤(pán)從塔座x移到塔座y的頂部

cout<<"Thedisk"<<n<<"ismovedfrom" <<char(x)<<"totopoftower"<<char(y)<<endl;}

voidHanoi(intn,towerx,towery,towerz){//將x上部的n個(gè)圓盤(pán)移到y(tǒng)上，順序不變。

if(n){ Hanoi(n-1,x,z,y); Move(n,x,y); Hanoi(n-1,z,y,x); }}1.4.3歸納證明定理1-1對(duì)于n≥0，程序1-5是正確的。

證明：（歸納法證明）當(dāng)n是1位數(shù)時(shí)，程序顯然是正確的。假定函數(shù)PrintDigit對(duì)所有位數(shù)小于k（k＞1）的正整數(shù)都能正確運(yùn)行，當(dāng)n的位數(shù)為k位時(shí)，此時(shí)有n≥10，算法必定先執(zhí)行語(yǔ)句cout<<n%10;然后執(zhí)行語(yǔ)句if(n>

10)PrintDigit(n/10);。

由于

n/10

是n的前k-1位數(shù)字形成的數(shù)，歸納法假設(shè)函數(shù)調(diào)用PrintDigit(n/10)能夠?qū)⑺_地（并在有限步內(nèi)）按數(shù)字的逆序輸出，那么，現(xiàn)在先執(zhí)行語(yǔ)句輸出個(gè)位數(shù)字（n%10），然后由于按逆序輸出前k-1位數(shù)字的做法是能夠正確按逆序輸出全部k位數(shù)字的，所以程序1-5是正確的。算法設(shè)計(jì)與分析

——C++語(yǔ)言描述DeSignandAnalysisofAlgorithmsInC++

第2章算法分析基礎(chǔ)

2.1算法復(fù)雜度2.2漸近表示法

2.3遞推關(guān)系2.4分?jǐn)偡治?.1算法復(fù)雜度

2.1.1什么是好的算法

好的算法一個(gè)好的算法應(yīng)具有以下4個(gè)重要特性:正確性（correctness）：算法的執(zhí)行結(jié)果應(yīng)當(dāng)滿足預(yù)先規(guī)定的功能和性能要求。簡(jiǎn)明性（simplicity）：算法應(yīng)思路清晰、層次分明、容易理解、利于編碼和調(diào)試。效率（efficiency）：算法應(yīng)有效使用存儲(chǔ)空間，并具有高的時(shí)間效率。最優(yōu)性（optimality）：算法的執(zhí)行時(shí)間已達(dá)到求解該類(lèi)問(wèn)題所需時(shí)間的下界。

程序健壯性是指當(dāng)輸入不合法數(shù)據(jù)時(shí)，程序應(yīng)能做適當(dāng)處理而不至于引起嚴(yán)重后果。其含義是：當(dāng)程序萬(wàn)一遇到意外時(shí)，能按某種預(yù)定方式做出適當(dāng)處理。正確性和健壯性是相互補(bǔ)充的。

2.1.2影響程序運(yùn)行時(shí)間的因素影響程序運(yùn)行時(shí)間的因素主要有：程序所依賴的算法；問(wèn)題規(guī)模和輸入數(shù)據(jù)；計(jì)算機(jī)系統(tǒng)性能。

2.1.3算法的時(shí)間復(fù)雜度

抽象機(jī)模型設(shè)抽象機(jī)提供由m個(gè)基本運(yùn)算（也可稱為語(yǔ)句）組成的運(yùn)算集O={O1,O2,…,Om}，每個(gè)運(yùn)算都是基本的，它們的執(zhí)行時(shí)間是有限常量。同時(shí)設(shè)執(zhí)行第i個(gè)運(yùn)算Oi所需的時(shí)間是

i，1≤i≤m。

時(shí)間復(fù)雜度一個(gè)算法的時(shí)間復(fù)雜度（timecomplexity）是指算法運(yùn)行所需的時(shí)間。設(shè)有一個(gè)在抽象機(jī)上運(yùn)行的算法A，I是某次運(yùn)行時(shí)的輸入數(shù)據(jù)，其規(guī)模為n，則算法A的運(yùn)行時(shí)間T是n和I的函數(shù)，記做T(n,I)。又設(shè)在該次運(yùn)算中抽象機(jī)的第i個(gè)基本運(yùn)算Oi的執(zhí)行次數(shù)為

i，1≤i≤m，

i也是n和I的函數(shù)，記做

i(n,I)。那么，算法A在輸入為I時(shí)的運(yùn)行時(shí)間是：

設(shè)有一個(gè)在抽象機(jī)上運(yùn)行的算法A，I是某次運(yùn)行時(shí)的輸入數(shù)據(jù)，其規(guī)模為n，則算法A的運(yùn)行時(shí)間T是n和I的函數(shù)，記做T(n,I)。又設(shè)在該次運(yùn)算中抽象機(jī)的第i個(gè)基本運(yùn)算Oi的執(zhí)行次數(shù)為

i，1≤i≤m，

i也是n和I的函數(shù)，記做

i(n,I)。那么，算法A在輸入為I時(shí)的運(yùn)行時(shí)間是：最好、最壞和平均時(shí)間復(fù)雜度最好時(shí)間復(fù)雜度最壞時(shí)間復(fù)雜度平均時(shí)間復(fù)雜度

2.1.4使用程序步分析算法

一個(gè)程序步（programstep）是指在語(yǔ)法上或語(yǔ)義上有意義的程序段，該程序段的執(zhí)行時(shí)間必須與問(wèn)題實(shí)例的規(guī)模無(wú)關(guān)。例子

【程序2-1】

求數(shù)組元素累加之和的迭代程序floatSum(floatlist[],constintn){floattempsum=0.0;count++;//針對(duì)賦值語(yǔ)句

for(inti=0;i<n;i++){count++; //針對(duì)for循環(huán)語(yǔ)句

tempsum+=list[i];count++; //針對(duì)賦值語(yǔ)句

}count++;//針對(duì)for的最后一次執(zhí)行

count++; //針對(duì)return語(yǔ)句

returntempsum;}

設(shè)RSum（list,n）的程序步為T(mén)(n)

T(n)=2+T(n-1)=2+2+T(n-2)=2*3+T(n-3)

=2*n+T(0)=2*n+2

【程序2-2】求數(shù)組元素累加之和的遞歸程序floatRSum(floatlist[],constintn){count++;//針對(duì)if條件

if(n){count++;//針對(duì)RSum調(diào)用和return語(yǔ)句

returnRSum(list,n-1)+list[n-1];}count++; //針對(duì)return語(yǔ)句

return0;}

【程序1-2】

歐幾里德迭代算法intGcd(intm,intn){ if(m==0)returnn;if(n==0)returnm; if(m>n)Swap(m,n); while(m>0){ intc=n%m;n=m;m=c; } returnn;}2.1.5算法的空間復(fù)雜度

一個(gè)算法的空間復(fù)雜度（spacecomplexity）是指算法運(yùn)行所需的存儲(chǔ)空間。程序運(yùn)行所需的存儲(chǔ)空間包括以下兩部分：固定空間需求（fixedspacerequirement）這部分空間與所處理數(shù)據(jù)的大小和個(gè)數(shù)無(wú)關(guān)，也就是說(shuō)，與問(wèn)題實(shí)例的特征無(wú)關(guān)。可變空間需求（variablespacerequirement）這部分空間大小與算法在某次執(zhí)行中處理的特定數(shù)據(jù)的規(guī)模有關(guān)。

2.2漸近表示法

2.2.1大O記號(hào)定義2-1

設(shè)函數(shù)f(n)和g(n)是定義在非負(fù)整數(shù)集合上的正函數(shù)，如果存在兩個(gè)正常數(shù)c和n0，使得當(dāng)n≥n0時(shí)，有f(n)≤cg(n)，則記做f(n)=O(g(n))，稱為大O記號(hào)（bigOhnotation）。

例2-1f(n)=2n+3=O(n)當(dāng)n≥3時(shí)，2n+3≤3n，所以，可選c=3，n0=3。對(duì)于n≥n0，f(n)=2n+3≤3n，所以，f(n)=O(n)，即2n+3

O(n)。這意味著，當(dāng)n≥3時(shí)，程序2-1的程序步不會(huì)超過(guò)3n，2n+3=O(n)。

例2-2

f(n)=10n2+4n+2=O(n2)對(duì)于n≥2時(shí)，有10n2+4n+2≤10n2+5n，并且當(dāng)n≥5時(shí)，5n≤n2，因此，可選c=11,n0=5；對(duì)于n≥n0，f(n)=10n2+4n+2≤11n2，所以f(n)=O(n2)。

例2-3

f(n)=n！=O(nn)對(duì)于n≥1，有n(n

1)(n

2)…1≤nn，因此，可選c=1，n0=1。對(duì)于n≥n0，f(n)=n！≤nn，所以，f(n)=O(nn)。

例2-3

10n2+9

O(n)使用反證法，假定存在c和n0，使得對(duì)于n≥n0，10n2+9≤cn始終成立，那么有10n+9/n≤c，即n≤c/10

9/(10n)總成立。但此不等式不可能總成立，取n=c/10+1時(shí)，該不等式便不再成立。定理2-1

如果f(n)=amnm+am

1nm

1+…+a1n+a0是m次多項(xiàng)式，且am＞0，則f(n)=O(nm)。證明：取n0=1，當(dāng)n≥n0時(shí)，有

f(n)=amnm+am

1nm

1+

+a1n+a0

|am|nm+|am

1|nm

1+

+|a1|n+|a0|

(|am|+|am

1|/n+

+|a1|/nm

1+|a0|/nm)nm

(|am|+|am

1|+

+|a1|+|a0|)nm可取c=|am|+|am

1|+

+|a1|+|a0|，定理得證。

漸近時(shí)間復(fù)雜度使用大O記號(hào)及下面定義的幾種漸近表示法表示的算法時(shí)間復(fù)雜度，稱為算法的漸近時(shí)間復(fù)雜度（asymptoticcomplexity）。只要適當(dāng)選擇關(guān)鍵操作，算法的漸近時(shí)間復(fù)雜度可以由關(guān)鍵操作的執(zhí)行次數(shù)之和來(lái)計(jì)算。一般地，關(guān)鍵操作的執(zhí)行次數(shù)與問(wèn)題的規(guī)模有關(guān)，是n的函數(shù)。

【程序2-3】

矩陣乘法for（i=0;i<n;i++）//n+1for（j=0;j<n;j++）{//n(n+1)c[i][j]=0;//n2for（k=0;k<n;k++）//n2(n+1)c[i][j]+=a[i][k]*b[k][j];//n3}

2.2.2

記號(hào)定義2-2

設(shè)有函數(shù)f(n)和g(n)是定義在非負(fù)整數(shù)集合上的正函數(shù)，如果存在兩個(gè)正常數(shù)

c和n0，使得當(dāng)n≥n0時(shí)，有f(n)≥c

g(n)，則記做f(n)=

(g(n))，稱為

記號(hào)（omeganotation）。

例2-5f(n)=2n+3=

(n)對(duì)所有n，2n+3≥2n，可選c=2，n0=0。對(duì)于n≥n0，f(n)=2n+3≥2n，所以，f(n)=

(n)，即2n+3

(n)。

例2-6f(n)=10n2+4n+2=

(n2)對(duì)所有n，10n2+4n+2≥10n2，可選c=10，n0=0。對(duì)于n≥n0，f(n)=10n2+4n+2≥10n2，所以，f(n)=

(n2)。

定理2-3

如果f(n)=amnm+am

1nm

1+…+a1n+a0是m次多項(xiàng)式，且am＞0，則f(n)=

(nm)。2.2.3

記號(hào)定義2-3設(shè)有函數(shù)f(n)和g(n)是定義在非負(fù)整數(shù)集合上的正函數(shù)，如果存在正常數(shù)c1，c2和n0，使得當(dāng)n≥n0時(shí)，有c1g(n)≤f(n)≤c2

g(n)，則記做f(n)=

(g(n))，稱為

記號(hào)（Thetanotation）。

例2-7f(n)=2n+3=

(n)，即2n+3

(n)。例2-8f(n)=10n2+4n+2=

(n2)。定理2-4

如果f(n)=amnm+am

1nm

1+…+a1n+a0是m次多項(xiàng)式，且am＞0，則f(n)=

(nm)。2.2.4小o記號(hào)定義2-4f(n)=o(g(n))當(dāng)且僅當(dāng)f(n)=O(g(n))且f(n)

(g(n))例2-9

f(n)=2n+3=o(n2)，即2n+3

o(n2)。

2.2.5算法按時(shí)間復(fù)雜度分類(lèi)算法按計(jì)算時(shí)間分類(lèi)凡漸近時(shí)間復(fù)雜度有多項(xiàng)式時(shí)間限界的算法稱做多項(xiàng)式時(shí)間算法（polynomialtimealgorithm），而漸近時(shí)間復(fù)雜度為指數(shù)函數(shù)限界的算法稱做指數(shù)時(shí)間算法（exponentialtimealgorithm）。

最常見(jiàn)的多項(xiàng)式時(shí)間算法的漸近時(shí)間復(fù)雜度O(1)＜O(logn)＜O(n)＜O(nlog

n)＜O(n2)＜O(n3)最常見(jiàn)的指數(shù)時(shí)間算法的漸近時(shí)間復(fù)雜度O(2n)＜O(n！)＜O(nn)

2.3遞推關(guān)系

2.3.1遞推方程遞推方程（recurrenceequation）是自然數(shù)上一個(gè)函數(shù)T(n)，它使用一個(gè)或多個(gè)小于n時(shí)的值的等式或不等式來(lái)描述。遞推方程也稱為遞推關(guān)系或遞推式。遞推方程必須有一個(gè)初始條件（也稱邊界條件）。

例2-10程序1-5的時(shí)間分析設(shè)n=d1d2

dk是k位數(shù)，當(dāng)k=1時(shí)，只執(zhí)行cout語(yǔ)句和if判定語(yǔ)句；當(dāng)n至少是2位數(shù)（k＞1）時(shí)，除了執(zhí)行這兩個(gè)操作外，還需執(zhí)行遞歸函數(shù)調(diào)用PrintDigit(n/10)，

n/10

是k

1位數(shù)。

T(k)=2k+2=

(k)2.3.2替換方法替換方法要求首先猜測(cè)遞推式的解，然后用歸納法證明。例2-11

使用替換方法分析程序1-6?？梢韵葘?duì)以下這些小的示例進(jìn)行計(jì)算：T(3)=7=23

1；T(4)=15=24

1；T(5)=31=25

1；T(6)=63=26

1看起來(lái)，似乎T(n)=2n

1，n≥1。

證明：（歸納法證明）當(dāng)n=1時(shí)，T(1)=1，結(jié)論成立。歸納法假設(shè)：當(dāng)k＜n時(shí)，有T(k)=2k

1，那么，當(dāng)k=n時(shí)，T(n)=2T(n

1)+1=2(2n

1

1)+1=2n

1。因此，對(duì)所有n≥1，T(n)=2n

1=

(2n)。2.3.3迭代方法迭代方法的思想是擴(kuò)展遞推式，將遞推式先轉(zhuǎn)換成一個(gè)和式，然后計(jì)算該和式，得到漸近復(fù)雜度。例2-12

使用迭代方法分析程序1-6。函數(shù)Hanoi中兩次調(diào)用自身，函數(shù)調(diào)用使用的實(shí)在參數(shù)均為n

1，函數(shù)Move所需時(shí)間具有常數(shù)界

(1)，可以將其視為一個(gè)程序步，于是有：

擴(kuò)展并計(jì)算此遞推式：T(n)=2T(n

1)+1=2(2T(n

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

2)+2+1=23T(n

3)+22+2+1

=2n

1T(1)+…+22+2+1=2n

1+…+22+2+1=2n

1

使用遞歸樹(shù)（recursiontree）可以形象地看到遞推式的迭代過(guò)程。

例2-13

T(n)=2T(n/2)+n的遞歸樹(shù)

例2-14T(n)=T(n/3)+T(2n/3)+n的遞歸樹(shù)

2.3.4主方法

主方法在遞歸算法分析中，常需要求解如下形式的遞推式：T(n)=aT(n/b)+f(n)式中，a≥1和b＞1是常數(shù)，f(n)是一個(gè)漸近正函數(shù)，n/b指

n/b

或

n/b

。求解這類(lèi)遞推式的方法稱為主方法。

定理2-5

（主定理）設(shè)a≥1和b＞1為常數(shù)，f(n)是一個(gè)函數(shù)，T(n)由下面的遞推式定義T(n)=aT(n/b)+f(n)式中，n/b指

n/b

或

n/b

，則T(n)有如下的漸近界：（1）若對(duì)某常數(shù)

＞0，有f(n)=O()，則T(n)=

()；（2）若f(n)=

()，則T(n)=

(logn)；（3）若對(duì)某常數(shù)

＞0，有f(n)=

()，且對(duì)某個(gè)常數(shù)c＜1和所有足夠大的n，有af(n/b)≤cf(n)，則T(n)=

(f(n))。

例2-15T(n)=16T(n/4)+n因?yàn)閍=16,b=4,=n2,f(n)=n=O()=O(n2

)，其中，

=1與主定理的情況（1）相符合，T(n)=

()=

(n2)。例2-16T(n)=T(3n/7)+1因?yàn)閍=1,b=7/3,==n0=1,f(n)=1=

()，所以，符合主定理情況（2），T(n)=

(logn)=

(logn)。例2-17T(n)=3T(n/4)+nlogn因?yàn)閍=3,b=4,==O(n0.793),f(n)=nlogn=

，其中，

≈0.2。由于對(duì)足夠大的n，3(n/4)log(n/4)≤(3/4)nlogn，這里c=3/4，符合主定理情況（3）。T(n)=

(f(n))=

(nlogn)。

例2-18T(n)=2T(n/2)+nlogn由于a=2,b=2,f(n)=nlogn和=n?？雌饋?lái)似乎屬于主定理情況（3），但事實(shí)上不是。因?yàn)閒(n)只是漸近大于n，但并不是多項(xiàng)式大于n。f(n)與的比值是logn，對(duì)于任何正數(shù)

，logn漸近小于n

，所以，此例不能運(yùn)用主定理。

算法設(shè)計(jì)與分析

——C++語(yǔ)言描述DeSignandAnalysisofAlgorithmsInC++

第2部分算法設(shè)計(jì)策略

第5章分治法

5.1

分治法的基本思想5.2

求最大最小元 5.3

二分搜索5.4

排序問(wèn)題5.5選擇問(wèn)題5.6斯特拉森矩陣乘法

5.1一般方法

5.1.1分治法的基本思想

分治法顧名思義就是分而治之。一個(gè)問(wèn)題能夠用分治法求解的要素是：第一，問(wèn)題能夠按照某種方式分解成若干個(gè)規(guī)模較小、相互獨(dú)立且與原問(wèn)題類(lèi)型相同的子問(wèn)題；第二，子問(wèn)題足夠小時(shí)可以直接求解；第三，能夠?qū)⒆訂?wèn)題的解組合成原問(wèn)題的解。由于分治法要求分解成同類(lèi)子問(wèn)題，并允許不斷分解，使問(wèn)題規(guī)模逐步減小，最終可用已知的方法求解足夠小的問(wèn)題，因此，分治法求解很自然導(dǎo)致一個(gè)遞歸算法。

【程序5-1】

分治法SolutionTypeDandC(ProblemTypeP){ ProblemTypeP1，P2，

，Pk; if(Small(P))returnS(P); else{ Divide(P，P1，P2，

，Pk); ReturnCombine(DandC(P1)，

DandC(P2)，…，DandC(Pk)); }}

【程序5-2】

一分為二的分治法SolutionTypeDandC(intleft，intright){ if(Small(left,right))returnS(left,right); else{ intm=Divide(left，right); ReturnCombine(DandC(left，m)，

DandC(m+1，right)); }}5.1.2算法分析

采用分治法求解問(wèn)題通常得到一個(gè)遞歸算法。如果較大的問(wèn)題被分解成同樣大小的幾部分，那么分析相應(yīng)算法的執(zhí)行時(shí)間，往往可得到如下的遞推關(guān)系式：T(n)=aT(n/b)+cnk，T(1)=c

定理5-1設(shè)a,b,c和k為常數(shù)，T(n)=aT(n/b)+cnk，T(1)=c，則，

設(shè)r=bk/a，下面分三種情況計(jì)算。（1）若r<1，則

所以（2）若r=1，則

所以（3）若r>1，則

所以

5.1.3

數(shù)據(jù)結(jié)構(gòu)【程序5－3】可排序表類(lèi)template<classK,classD>structE{//可排序表中元素的類(lèi)型

operatorK()const{returnkey;}Kkey;Ddata;};

template<classT>classSortableList{//可排序表類(lèi)public:SortableList(intmSize);~SortableList();

private:

T*l;intmaxSize;intn;};

5.2求最大最小元

問(wèn)題在一個(gè)元素集合中尋找最大元素和最小元素的問(wèn)題。5.2.1

分治法求解

【程序5－4】求最大最小元template<classT>voidSortableList<T>::MaxMin(T&max,T&min)const{ if(n==0)return; max=min=l[0]; for(inti=1;i<n;i++){ if(l[i]>max)max=l[i]; if(l[i]<min)min=l[i]; }}

【程序5－5】分治法求最大最小元template<classT>voidSortableList<T>::MaxMin(inti,intj,T&max,T&min)const{ Tmin1,max1; if(i==j)max=min=l[i];elseif(i==j-1) if(l[i]<l[j]){ max=l[j];min=l[i]; } else{ max=l[i];min=l[j]; }

else{ intm=(i+j)/2; MaxMin(i,m,max,min); MaxMin(m+1,j,max1,min1); if(max<max1)max=max1; if(min>min1)min=min1; }}

5.2.2時(shí)間分析定理5－2

設(shè)有n個(gè)元素的表，假定n是2的冪，即n=2k，k是正整數(shù)，程序5－5在最好、平均和最壞情況下的比較次數(shù)都為3n/2–2。

5.3二分搜索

問(wèn)題在有序表（已按關(guān)鍵字值非減排序）中搜索給定元素的問(wèn)題。5.3.1

分治法求解

intSortableList<T>::BSearch(constT&x,intleft,intright)const后置條件:

在范圍為[left,right]的表中搜索與x有相同關(guān)鍵字值的元素；如果存在該元素，則函數(shù)返回該元素在表中的位置，否則函數(shù)返回－1，表示搜索失敗?！境绦?－6】二分搜索算法框架template<classT>intSortableList<T>::BSearch(constT&x,intleft,intright)const{ if(left<=right){intm=Divide(left+right);if(x<l[m])returnBSearch(x,left,m-1); elseif(x>l[m])returnBSearch(x,m+1,right); elsereturnm;}return-1;}

5.3.2

對(duì)半搜索

對(duì)半搜索對(duì)半搜索是一種二分搜索。設(shè)當(dāng)前搜索的子表為（aleft,aleft+1,…,aright），令

m=(left+right)/2

【程序5－7】對(duì)半搜索遞歸算法template<classT>intSortableList<T>::BSearch(constT&x,intleft,intright)const{if(left<=right){intm=(left+right)/2;if(x<l[m])returnBSearch(x,left,m-1); elseif(x>l[m])returnBSearch(x,m+1,right);elsereturnm;}return-1;}定理5－3對(duì)于n

0，程序5－7的對(duì)半搜索遞歸函數(shù)BSearch是正確的。

5.3.3

二叉判定樹(shù)

二分搜索過(guò)程的算法行為可以用一棵二叉樹(shù)來(lái)描述。通常稱這棵描述搜索算法執(zhí)行過(guò)程的二叉樹(shù)為二叉判定樹(shù)(binarydecisiontree)。

性質(zhì)5－1

具有n個(gè)內(nèi)結(jié)點(diǎn)的對(duì)半搜索二叉判定樹(shù)的左子樹(shù)上有

(n-1)/2

個(gè)內(nèi)結(jié)點(diǎn)，右子樹(shù)上有

n/2

個(gè)內(nèi)結(jié)點(diǎn)。

性質(zhì)5－2

具有n(n>0）個(gè)內(nèi)結(jié)點(diǎn)的二叉判定樹(shù)的高度為

logn

+1

（不計(jì)外結(jié)點(diǎn)）。

性質(zhì)5－3

若n=2h-1，則對(duì)半搜索二叉判定樹(shù)是滿二叉樹(shù)。

性質(zhì)5－4

若n=2h-1，則對(duì)半搜索二叉判定樹(shù)的外結(jié)點(diǎn)均在h+1層上，否則，在第h或h+1層上，h=

logn

+1。

定理5－4

對(duì)半搜索算法在成功搜索的情況下，關(guān)鍵字值之間的比較次數(shù)不超過(guò)

logn

+1。對(duì)于不成功的搜索，算法需要作

logn

或

logn

+1次比較。定理5－5

對(duì)半搜索算法在搜索成功時(shí)的平均時(shí)間復(fù)雜度為

(logn)。

5.3.4搜索算法的時(shí)間下界

定理5－6

在一個(gè)有n個(gè)元素的集合中，通過(guò)關(guān)鍵字值之間的比較，搜索指定關(guān)鍵字值的元素，任意這樣的算法在最壞情況下至少需要作

log

n

+1次比較。

5.4排序問(wèn)題

問(wèn)題排序是將一個(gè)元素序列調(diào)整為按指定關(guān)鍵字值的遞增（或遞減）次序排列的有序序列。

5.4.1

合并排序

合并兩個(gè)有序序列

兩路合并排序的基本運(yùn)算是把兩個(gè)有序序列合并成一個(gè)有序序列。

【程序5－9】Merge函數(shù)template<classT>voidSortableList<T>::Merge(intleft,intmid,intright){ T*temp=newT[right-left+1];inti=left,j=mid+1,k=0;while((i<=mid)&&(j<=right)) if(l[i]<=l[j])temp[k++]=l[i++];elsetemp[k++]=l[j++];while(i<=mid)temp[k++]=l[i++];while(j<=right)temp[k++]=l[j++]; for(i=0,k=left;k<=right;)l[k++]=temp[i++];}

分治法求解將待排序的元素序列一分為二分，得到兩個(gè)長(zhǎng)度基本相等的子序列，如同對(duì)半搜索的做法；然后對(duì)兩個(gè)子序列分別排序，如果子序列較長(zhǎng)，還可繼續(xù)細(xì)分，直到子序列的長(zhǎng)度不超過(guò)1為止；當(dāng)分解所得的子序列已排列有序，可以采用上面介紹的將兩個(gè)有序子序列，合并成一個(gè)有序子序列的方法，實(shí)現(xiàn)將子問(wèn)題的解組合成原問(wèn)題解，這是分治法不可缺少的一步。

【程序5－10】?jī)陕泛喜⑴判騮emplate<classT>voidSortableList<T>::MergeSort(intleft,intright){if(left<right){intmid=(left+right)/2;MergeSort(left,mid);MergeSort(mid+1,right);Merge(left,mid,right);}}

template<classT>voidSortableList<T>::MergeSort(){ MergeSort(0,n-1);}

性能分析合并排序遞歸算法的時(shí)間復(fù)雜度為O(nlog

n)。

5.4.2

快速排序快速排序采用一種特殊的分劃操作對(duì)排序問(wèn)題進(jìn)行分解，其分解方法是：在待排序的序列(K0,K1,…,Kn-1)中選擇一個(gè)元素作為分劃元素，也稱為主元（pivot）。不妨假定選擇K

為主元。經(jīng)過(guò)一趟特殊的分劃處理將原序列中的元素重新排列，使得以主元為軸心，將序列分成左右兩個(gè)子序列。主元左測(cè)子序列中所有元素都不大于主元，主元右測(cè)子序列中所有元素都不小于主元。

分劃操作

【程序5－11】

分劃函數(shù)template<classT>intSortableList<T>::Partition(intleft,intright){//前置條件：left

right inti=left,j=right+1;do{doi++;while(l[i]<l[left]);doj--;while(l[j]>l[left]);if(i<j)Swap(i,j);}while(i<j); Swap(left,j); returnj;}快速排序算法

【程序5－12】快速排序template<classT>voidSortableList<T>::QuickSort(){QuickSort(0,n-1);}template<classT>voidSortableList<T>::QuickSort(intleft,intright){ if(left<right){intj=Partition(left,right);QuickSort(left,j-1); QuickSort(j+1,right); }}

時(shí)間分析最壞情況時(shí)間

W(n)

W(n-1)+n+1

W(n-2)+(n+1)+n

W(1)+(n+1)+

+3=O(n2)

平均情況時(shí)間

5.4.3排序算法的時(shí)間下界定理5－7

任何一個(gè)通過(guò)關(guān)鍵字值比較對(duì)n個(gè)元素進(jìn)行排序的算法，在最壞情況下，至少需作（n/4）log

n次比較。

5.5選擇問(wèn)題

問(wèn)題選擇問(wèn)題（selectproblem）是指在n個(gè)元素的集合中，選出某個(gè)元素值大小在集合中處于第k位的元素，即所謂的求第k小元素問(wèn)題(kth-smallest)。

5.5.1

分治法求解

設(shè)原表長(zhǎng)度為n，假定經(jīng)過(guò)一趟分劃，分成兩個(gè)左右子表，其中左子表是主元及其左邊元素的子表，設(shè)其長(zhǎng)度為p，右子表是主元右邊元素的子表。那么，若k=p，則主元就是第k小元素；否則若k<p，第k小元素必定在左子表中，需求解的子問(wèn)題成為在左子表中求第k小元素；若k>p，則第k小元素必定在右子表中，需求解的子問(wèn)題成為在右子表中求第k-p小元素。

5.5.2

隨機(jī)選擇主元

隨機(jī)選主元算法

假定表中元素各不相同，并且隨機(jī)選擇主元，即在下標(biāo)區(qū)間[left,right]中隨機(jī)選擇一個(gè)下標(biāo)r，以該下標(biāo)處的元素為主元。

【程序5－13】Select函數(shù)template<classT>ResultCodeSortableList<T>::Select1(T&x,intk){if(n<=0||k>n||k<=0)returnOutOfBounds;intleft=0,right=n;l[n]=INFTY;do{ intj=rand()%(right-left+1)+left; Swap(left,j); j=Partition(left,right); if(k==j+1){x=l[j];returnSuccess;} elseif(k<j+1)right=j; elseleft=j+1; }while(true);}

定理5－8

程序5－13的Select算法的平均時(shí)間A(n)=O(n)。算法的最壞情況時(shí)間復(fù)雜度O(n2)。5.5.3

線性時(shí)間選擇算法改進(jìn)的選擇算法采用二次取中法(medianofmediansrule)確定主元

【程序5－14】線性時(shí)間選擇算法ResultCodeSortableList<T>::Select(T&x,intk){ if(n<=0||k>n||k<=0)returnOutOfBounds; intj=Select(k,0,n-1,5); x=l[j];returnSuccess;}

template<classT>intSortableList<T>::Select(intk,intleft,intright,intr){intn=right-left+1;if(n<=r){InsertSort(left,right);returnleft+k-1;

}

for(inti=1;i<=n/r;i++){InsertSort(left+(i-1)*r,left+i*r-1);Swap(left+i-1,left+(i-1)*r+Ceil(r,2)-1);}intj=Select(Ceil(n/r,2),left,left+(n/r)-1,r);Swap(left,j);j=Partition(left,right);if(k==j-left+1)returnj;elseif(k<j-left+1)returnSelect(k,left,j-1,r);elsereturnSelect(k-(j-left+1),j+1,right,r);}5.5.4時(shí)間分析

以二次取中的中間值mm為主元，經(jīng)過(guò)一趟分劃，左、右兩個(gè)子表的大小均至多為：

n

n/r

/2

r/2

設(shè)T(n)為當(dāng)表長(zhǎng)為n時(shí)執(zhí)行程序5－14所需的時(shí)間。T(n)由三部分時(shí)間組成：

T(n)

T(

n/5

)+T(3n/4)+cn

用歸納法容易證明，T(n)

20cn，n

1是線性時(shí)間的。

5.5.5允許重復(fù)元素的選擇算法由于允許包含相同元素，左子表中除了小于mm的元素外，還包含與mm相同值的元素。因此，左子表的大小至多可達(dá)

n

n/r

/2

r/2

+1/2

n/r

/2

r/2

=n-1/2

n/r

/2

r/2

容易用歸納法證明對(duì)于所有n

90，

T(n)

T(n/9)+T(7n/8)+cn

72cn，n

90

5.6斯特拉森矩陣乘法

問(wèn)題矩陣相乘

5.6.1分治法求解

C11＝A11B11+A12B21C12＝A11B12+A12B22C21＝A21B11+A22B21C22＝A21B12+A22B22

T(n)=

(n3)5.6.2

斯特拉森分治法P=(A11+A22)(B11+B22)Q=(A21+A22)B11R=A11(B12-B22)S=A21(B21-B11)T=(A11+A12)B22U=(A21-A11)(B11+B12)V=(A12-A22)(B21+B22)

C11=P+S-T+VC12=R+TC21=Q+SC22=P+R-Q+UT(n)=

(nlog7)

(n2.81)

算法設(shè)計(jì)與分析

——C++語(yǔ)言描述DeSignandAnalysisofAlgorithmsInC++

第2部分算法設(shè)計(jì)策略

第6章貪心法

6.1一般方法

6.2背包問(wèn)題

6.3帶時(shí)限的作業(yè)排序

6.4最佳合并模式

6.5最小代價(jià)生成樹(shù)

6.6單源最短路徑

6.7磁帶最優(yōu)存儲(chǔ)

6.8貪心法的基本要素6.1一般方法

最優(yōu)化問(wèn)題（optimizationproblems）是指這樣一類(lèi)問(wèn)題，問(wèn)題給定某些約束條件（constraint），滿足這些約束條件的問(wèn)題解稱為可行解（feasiblesolution）。通常滿足約束條件的解不是惟一的。為了衡量可行解的好壞，問(wèn)題還給出了某個(gè)數(shù)值函數(shù)，稱為目標(biāo)函數(shù)（objectivefunction），使目標(biāo)函數(shù)取最大（或最小）值的可行解稱為最優(yōu)解（optimalsolution）。

貪心法是通過(guò)分步?jīng)Q策（stepwisedecision）的方法來(lái)求解問(wèn)題的。貪心法每一步上用作決策依據(jù)的選擇準(zhǔn)則被稱為最優(yōu)量度標(biāo)準(zhǔn)（optimizationcriterion）。在根據(jù)最優(yōu)量度標(biāo)準(zhǔn)選擇分量的過(guò)程中，還需要使用一個(gè)可行解判定函數(shù)。貪心策略并不是從整體上加以考慮的，它所做出的選擇只是當(dāng)前看似最佳選擇，必須進(jìn)一步證明該算法最終導(dǎo)致問(wèn)題的一個(gè)整體最優(yōu)解。

【程序6－1】貪心法SolutionTypeGreedy(STypea[],intn){ SolutionTypesolution=

; for(inti=0;i<n;i++){ STypex=Select(a); if(Feasiable(solution,x)) solution=Union(solution,x); } returnsolution;}6.2背包問(wèn)題

問(wèn)題在一個(gè)元素集合中尋找最大元素和最小元素的問(wèn)題。6.2.1

問(wèn)題描述

已知一個(gè)載重為M的背包和n件物品，第i件物品的重量為wi，如果將第i件物品全部裝入背包，將有收益pi，這里，wi>0，pi>0，0

i<n。所謂背包問(wèn)題是指求一種最佳裝載方案，使得收益最大。所以，背包問(wèn)題是現(xiàn)實(shí)世界一個(gè)常見(jiàn)的最優(yōu)化問(wèn)題。兩類(lèi)背包問(wèn)題:如果每一件物品不能分割，只能作為整體或者裝入背包，或者不裝入，稱為0/1背包問(wèn)題；如果物品是可以分割的，也就是允許將其中的一部分裝入背包為一般背包問(wèn)題或簡(jiǎn)稱背包問(wèn)題。6.2.2貪心法求解

背包問(wèn)題背包問(wèn)題的解可以表示成一個(gè)n-元組：X=(x0,x1,

,xn－1)，0

xi

1，0

i<n，每個(gè)xi是第i件物品裝入背包中的部分。判定可行解的約束條件是：

背包問(wèn)題的最優(yōu)解必須使下列目標(biāo)函數(shù)取最大值：

例6－1

設(shè)有載重能力M=20的背包，3件物品的重量為:（w0,w1,w2）=(18,15,10)，物品裝入背包的收益為：（p0,p1,p2）=(25,24,15)。

【程序6－2】背包問(wèn)題的貪心算法

template<classT>classKnapsack{public: Knapsack(intmSize,floatcap,float*wei,T*prof);voidGreedyKnapsack(float*x);……private:floatm,*w;T*p;intn;};

template<classT>voidKnapsack<T>::GreedyKnapsack(float*x){//前置條件：w[i]已按p[i]/w[i]的非增次序排列

floatu=m;for(inti=0;i<n;i++)x[i]=0; for(i=0;i<n;i++){ if(w[i]>u)break; x[i]=1.0; u=u-w[i]; } if(i<=n)x[i]=u/w[i];}

6.2.3

算法正確性

定理6－1

如果p0/w0

p1/w1

pn－1/wn－1，則程序6－2求得的背包問(wèn)題的解是最優(yōu)解。

6.3帶時(shí)限的作業(yè)排序

6.3.1

問(wèn)題描述設(shè)有一個(gè)單機(jī)系統(tǒng)、無(wú)其它資源限制且每個(gè)作業(yè)運(yùn)行相等時(shí)間，不妨假定每個(gè)作業(yè)運(yùn)行1個(gè)單位時(shí)間?，F(xiàn)有n個(gè)作業(yè)，每個(gè)作業(yè)都有一個(gè)截止期限di>0，di為整數(shù)。如果作業(yè)能夠在截止期限之內(nèi)完成，可獲得pi>0的收益。問(wèn)題要求得到一種作業(yè)調(diào)度方案，該方案給出作業(yè)的一個(gè)子集和該作業(yè)子集的一種排列，使得若按照這種排列次序調(diào)度作業(yè)運(yùn)行，該子集中的每個(gè)作業(yè)都能如期完成，并且能夠獲得最大收益。也就是說(shuō)這種作業(yè)調(diào)度是最優(yōu)的。

6.3.2貪心法求解

例6－2設(shè)有4個(gè)作業(yè)，每個(gè)作業(yè)的時(shí)限為(d0,d1,d2,d3)=(2,1,2,1),收益為(p0,p1,p2,p3)=(100,10,15,27)。

【程序6－3】帶時(shí)限作業(yè)排序的貪心算法

voidGreedyJob(intd[],SetX,intn){//前置條件：p0

p1

,…,

pn-1

X={0};for(inti=1;i<n;i++)if(集合X

{i}中作業(yè)都能在給定時(shí)限內(nèi)完成)X=X

{i};}

6.3.3

算法正確性定理6－2程序6－2的貪心算法對(duì)于帶時(shí)限作業(yè)排序問(wèn)題將得到最優(yōu)解。

6.3.4

可行性判定

定理6－3X=（x0,x1,…,xk）是k個(gè)作業(yè)的集合，

=（

0,

1,…,

k）是X的一種特定排列，它使得，其中，是作業(yè)

j的時(shí)限。X是一個(gè)可行解當(dāng)且僅當(dāng)X中的作業(yè)能夠按

次序調(diào)度而不會(huì)有作業(yè)超期。

6.3.5

作業(yè)排序貪心算法

定理6－3提供了一種高效的可行解判定方法。使得在按最優(yōu)量度標(biāo)準(zhǔn)，即按作業(yè)收益的非增次序選擇下一