北京工業(yè)大學(xué)算法設(shè)計分析一紙開卷

1、時間復(fù)雜性分析：以語句為單位；統(tǒng)計基本語句的執(zhí)行次數(shù)；每執(zhí)行一次，認(rèn)為是一個時間單位。O的定義：如果存在正常數(shù)c和自然數(shù)n0，使得當(dāng)nn0時有f(n) cg(n)，則稱函數(shù)f(n)當(dāng)n充分大時上有界，且g(n)是它的一個上界，記f(n)= O(g(n)。的定義當(dāng)n n0時有f(n) cg(n)，記為f(n)=(g(n)的定義：當(dāng)n n0時，c1g(n) f(n) c2g(n)則記f(n)= (g(n)。即f(n)與g(n)同階。1.根據(jù)符號O的定義，存在正常數(shù)Ci和自然數(shù)Ni，使得對所有的n>=N有i=1.2，f（n）<=C1s(n)，g(n) <=C2r(n)所以 f（n）

2、+ g(n) <= C1s(n)+ C2r(n)，f（n）*g(n)<= C1C2s(n)r(n)；令 C3=max（C1,C2），C4=C1C2；則：f（n）+ g(n) <= C3s(n)+ r(n)=O(s(n)+ r(n)f（n）*g(n) <= C4*s(n)*r(n)=O(s(n)* r(n)分治算法的基本思想：是將一個規(guī)模為n的問題分解為a個規(guī)模較小的子問題，遞歸地解這些子問題，然后將各個子問題的解合并得到原問題的解。貪心算法的設(shè)計思路是：總是做出在當(dāng)前看來最好的選擇，即貪心算法并不是從整體最優(yōu)考慮，它所做的選擇只是在某種意義上的局部最優(yōu)選擇。貪心法的基本

3、要素：1. 貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。2.最優(yōu)子結(jié)構(gòu)性質(zhì)：當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。貪心算法與動態(tài)規(guī)劃算法的差異：共同點(diǎn)：求解的問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)。差異點(diǎn)：動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每做一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。動態(tài)規(guī)劃算法:保存已解決的子問題的答案，在需要時找出已求得的答案，以避免大量的重復(fù)計算，從而得到多項(xiàng)

4、式時間算法。基本步驟：找出最優(yōu)解的性質(zhì)，并描述其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式計算出最優(yōu)值。根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。2. 假設(shè)某算法在輸入規(guī)模為n時的計算時間為：T（n）=3*2n ，在A型計算機(jī)上實(shí)現(xiàn)并完成該算法的時間為t秒，現(xiàn)有更先進(jìn)的B型計算機(jī)，其運(yùn)算速度為A型計算機(jī)的64倍。試求出若在先進(jìn)的B型機(jī)上運(yùn)行同一算法在則T秒內(nèi)能求解輸入規(guī)模為多大的問題？ 64*3*2n=26*3*2n=3*2(n+6)；T=T(n)=3*2n n=log2(T/3)設(shè)新機(jī)器輸入規(guī)模為n1,則：n1=log2(3*2(n+6)/3)=n+6 3. 試說明為什么“在現(xiàn)代計算機(jī)上運(yùn)行

5、指數(shù)（如2n）時間算法是不可能的，要想在順序處理機(jī)上擴(kuò)大所處理問題的規(guī)模，有效的途徑是降低算法計算復(fù)雜度的數(shù)量級，而不是提高計算機(jī)的速度”。一個計算時間為(1)的算法，它的基本運(yùn)算執(zhí)行的次數(shù)是固定的，因此，總的時間由一個常數(shù)(即，零次多項(xiàng)式)來限界，而一個時間為(n2)的算法則由一個二次多項(xiàng)式來限界。多項(xiàng)式時間關(guān)系為(1)(log2n)(n)(nlog2n)(n2)(nn)指數(shù)時間關(guān)系為(2n)(n!)(nn)。當(dāng)n取得很大時，指數(shù)時間算法和多項(xiàng)式時間算法在所需時間上非常懸殊，對于任意的m0，總可以找到n0，當(dāng)nn0時，有2nnm。因此，只要有人能將現(xiàn)有指數(shù)時間算法中的任何一個算法簡化為多項(xiàng)式

6、時間算法，那就取得了一個偉大的成就。由這些結(jié)果可看出，當(dāng)數(shù)據(jù)集的規(guī)模(即n的取值)很大時，要在現(xiàn)代計算機(jī)上運(yùn)行具有比(nlog2n)復(fù)雜度還高的算法往往是很困難的。尤其是指數(shù)時間算法，它只有在n值取得非常小時才實(shí)用。要想在順序處理機(jī)上擴(kuò)大所處理問題的規(guī)模，有效的途徑是降低算法的計算復(fù)雜度的數(shù)量級，而不是提高計算機(jī)的速度。1.試用簡短的語言說明“建立一個問題復(fù)雜性的下界要比確定它的上界困難得多！”其復(fù)雜性上界是已知求解該問題的最快算法的費(fèi)用，而復(fù)雜性下界只能通過理論證明來建立。尋求某個問題的計算復(fù)雜性上界，只要研究一個算法的復(fù)雜性即可。但是要尋求同一問題的計算復(fù)雜性下界，則必須考察所有的解決該問

7、題的算法，證明一個問題的復(fù)雜性下界就需要證明不存在任何復(fù)雜性低于下界的算法。2.滿足何種性質(zhì)的問題被稱為稱為NP完全問題？請簡述研究NP完全問題的意義；（1）NP即是多項(xiàng)式復(fù)雜程度的非確定性問題。 而如果任何一個NP問題都能通過一個多項(xiàng)式時間算法轉(zhuǎn)換為某個NP問題，那么這個NP問題就稱為NP完全問題。如果一個NP完全問題能在多項(xiàng)式時間內(nèi)得到解決，那么NP中的每一個問題都可以在多項(xiàng)式時間內(nèi)解決。NP完全性理論的重要性:知道一個問題是NP完全的就給我們提供了有價值的信息，告訴我們采用什么樣的途徑可以是最富有成效的。一定不要去優(yōu)先尋找有效的、精確的算法。現(xiàn)在比較適當(dāng)?shù)耐緩绞羌芯χ铝τ谄渌^低目標(biāo)

8、的方法。尋找在大多數(shù)情況下看來能快速運(yùn)算的算法，雖然不能保證它在任何情況下都能快速地運(yùn)算。或者你甚至可以放松問題的某些方面，尋找一個只能給出滿足大部分要求的快速算法。簡言之，NP完全性理論的初步應(yīng)用是幫助算法設(shè)計人員找到最有可能得到有用的算法的努力方向 3.簡要闡述“論證某一問題的最優(yōu)子結(jié)構(gòu)性質(zhì)”時的一般方法；最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。在分析問題的最優(yōu)子結(jié)構(gòu)性質(zhì)時，首先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)的，然后再設(shè)法說明在這個假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導(dǎo)致矛盾。利用問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子問題的最優(yōu)解逐步構(gòu)造出整個

9、問題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是問題能用動態(tài)規(guī)劃算法求解的前提。證明0/1背包問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。證明：假設(shè)(x1,x2,.,xn-1)不是最優(yōu)解，而(y1,y2,.,yn-1)是最優(yōu)解。由此可知（寫公式）: 上述結(jié)果說明： (y1,y2,.,yn-1,xn)是所給0-1背包問題的更優(yōu)解。與前提矛盾。4.對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，我們必須證明每一步所作的貪心選擇最終導(dǎo)致問題的一個整體最優(yōu)解。首先考察問題的一個整體最優(yōu)解，并證明可修改這個最優(yōu)解，使其以貪心選擇開始。而且作了貪心選擇后，原問題簡化為一個規(guī)模更小的類似子問題。然后，用數(shù)學(xué)歸納法證明，通過每一步作貪心選擇，最終可得

10、到問題的一個整體最優(yōu)解。社會名流問題：給定一個n×n鄰接矩陣，確定是否存在一個i，其滿足在第i列所有項(xiàng)（除了第ii項(xiàng)）都為1，并且第i行所有項(xiàng)（除了第ii項(xiàng)）都為0。大致的算法思路：隨便取一個非對角線元素，比如Arrayij，如果Arrayij=0成立，則j不是社會名流，于是刪去第j行和第j列。同樣，如果Arrayij=1成立，則刪去第i行和第i列；總之，無論對應(yīng)項(xiàng)取何值，都可以刪去一行和一列，因此整個操作只耗費(fèi)O(n)的時間。重復(fù)此操作直至剩下最后一個元素。最后，檢驗(yàn)該元素是否為社會名流即可。如果該元素不是，則該群人中不存在社會名流。在最壞情況下用3n/2-2次的比較找出A中的最大

11、值和最小值使用一個快速排序的迭代模型可以使原遞歸算法所需的棧空間總量減至O（logn）struct nodeint low,high;st10000;void quicksort2(int data,int s,int t)int top=-1,low,high;top+;sttop.low=s;sttop.high=t;while(top>-1)low=sttop.low;high=sttop.high;top-;int w;if(low<high)w=split(data,low,high);/或者split2st+top.low=low;sttop.high=w-1;st+t

12、op.low=w+1;sttop.high=high; 4.試說明如何修改快速排序算法，使它在最壞情況下的計算時間為O(nlgn)。 可以通過減少遞歸棧的使用進(jìn)行優(yōu)化，快速排序的實(shí)現(xiàn)需要消耗遞歸棧的空間，而大多數(shù)情況下都會通過使用系統(tǒng)遞歸棧來完成遞歸求解。對系統(tǒng)棧的頻繁存取會影響到排序的效率。在數(shù)據(jù)量較大時，快速排序的復(fù)雜度為O(nlgn)。當(dāng)數(shù)據(jù)集較小時，快排的復(fù)雜度有向O(n2)發(fā)展的趨勢，此時不必繼續(xù)遞歸調(diào)用快速排序算法，使用插入排序代替快速排序。STL中sort就是用的快排+插入排序的，使得最壞情況下的時間復(fù)雜度也是O(nlgn)這一改進(jìn)被證明比持續(xù)使用快速排序算法要有效的多

13、。struct node int low,high;st10000; void quicksort2(int data,int s,int t) int top=-1,low,high; top+; sttop.low=s; sttop.high=t; while(top>-1) low=sttop.low; high=sttop.high;top-; int w; if(low<high)w=split(data,low,high);#include<stdio.h>#include<stdlib.h>#include "stdafx.

14、h"#include <iostream>using namespace std;int V200200;/前i個物品裝入容量為j的背包中獲得的最大價值int max(int a,int b)   if(a>=b)       return a;   else return b;int KnapSack(int n,in

15、t w,int v,int x,int C)    int i,j,t,k,lager,a,b;int K200200=0;    for(i=0;i<=n;i+) /邊界值 v(i,0)=v(0,j)=0;        Vi0=0;    for(j=0;j<=C;j+)   

16、60;    V0j=0;    for(j=1;j<=C;j+) /矩陣Vn+1C+1        for(i=1;i<=n;i+)           if(j<wi) /物品i的質(zhì)量大于背包容量         &

17、#160;       Vij=Vi-1j;  Kij=-1; /物品i放不下 else t=j/wi;lager=Vi-1j; /暫且認(rèn)為V(i-1,j)為最優(yōu)解,便于之后比較 for(k=1;k<=t;k+)b=Vi-1j-k*wi+k*vi;lager=max(lager,b); /最大價值 Vij=lager;if(Vij = Vi-1j)Kij=0; /物品i能放下,但非最優(yōu)解 elsefor(k=1;k<=t;k+)if(

18、Vij = Vi-1j-k*wi+k*vi)break;Kij=k; /物品i放入k次為最優(yōu)解 printf("matrix VnC is:n");for(i=0;i<=n;i+)for(j=0;j<=C;j+)printf("%3d ",Vij);printf("n");printf("matrix KnC is:n");for(i=0;i<=n;i+)for(j=0;j<=C;j+)printf("

19、%3d ",Kij);printf("n");    j=C;    for(i=n;i>=1;i-)             if(Vij=Vi-1j)         xi=0;      

20、            else                    xi=Kij;j=j-Kij*wi;               &

21、#160; printf("最優(yōu)裝法為:n");    for(i=1;i<=n;i+)        printf("%d ",xi);    printf("n");    return VnC;int main(int argc, char* argv)&#

22、160;   int s; /獲得的最大價值    int w15; /物品的重量    int v15; /物品的價值    int x15; /物品的選取狀態(tài)    int n,i;    int C; /背包最大容量    n=5;  

23、0; printf("背包的最大容量、可選物品種類:n");    /scanf("%d%d",&C,&n);cin>>C>>n;    printf("各物品的重量:n");    for(i=1;i<=n;i+)        cin>>wi;/scanf("

24、;%d",&wi);    printf("各物品的價值:n");    for(i=1;i<=n;i+)        cin>>vi;/scanf("%d",&vi);    s=KnapSack(n,w,v,x,C);    printf("背包能裝入的最大價

25、值為:n");    printf("%dn",s);    system("PAUSE"); return 0;TSP問題：數(shù)學(xué)語言描述：設(shè)需要經(jīng)過的城市為k=0,1,2,3,4; d(i, V)=minCik +  d(k, V-k)Cik表示你選擇的城市和城市i的距離，d(k, V-k)是一個子問題。廣義背包：數(shù)學(xué)語言描述：最優(yōu)子結(jié)構(gòu)性質(zhì)：，遞歸關(guān)系：。符號說明：vi第i個物品的價值，xi第i個物品的數(shù)量，wi第I 個物品的質(zhì)量。

26、將所求解的問題向下分解為左子問題和右子問題，分解的時候需要討論當(dāng)前商品是否在背包中，若在背包中則為右子問題，背包所剩的容量減去所選商品的質(zhì)量，若不在背包中則向下繼續(xù)分解，直到分解到最后一類商品或者背包容量為0以下。接下來向上遞歸，若背包中含有當(dāng)前商品，則加上次商品的價值，若不含，則向上遞歸，最終選取最大值作為最優(yōu)解。有編號分別為a,b,c,d,e的五件物品，它們的重量分別是2,2,6,5,4，它們的價值分別是6,3,5,4,6，現(xiàn)在給你個承重為10的背包，如何讓背包里裝入的物品具有最大的價值總和？nameweightvalue12345678910a26066991212151515b2303

27、3669991011c65000666661011d54000666661010e460006666666T(n)=2T(n/2)+n假設(shè)解對n/2成立，即T(n/2) c(n/2)lg(n/2)將其對遞歸方程進(jìn)行替換，得：T(n)= 2T(n/2)+n 2(c(n/2)lg(n/2)+n cnlg(n/2)+n cnlgn-cnlg2+n = cnlgn-cn+n 當(dāng)c1時，顯然cnlgn-cn+n cnlgn 根據(jù)O符號定義，證明猜測正確。T(n)=9T(n/3)+n由上式可知，a = 9，b = 3，f(n) = n,且又因?yàn)閷τ?有滿足定理（1），因此，T(n) = T(2n/3)+1由上式可知a=1, b=3/2, f(n)=1，且又因?yàn)闈M足定理（2），因此二分查找templat <class T>int binarySearch(T a, int x, int n) int left = 0;int right = n - 1;while (left <= right) int middle = (left + right)/2;if (x = amiddle) return middle;if (x &