1、期末總結(jié)基礎(chǔ)知識(shí)點(diǎn),1、概念（見教材） 2、漸進(jìn)分析 例題：寫出下列函數(shù)之間的大O、大或關(guān)系。,期末總結(jié)基礎(chǔ)知識(shí)點(diǎn),3、用展開法求解下列遞歸方程，將結(jié)果表示成大O形式。,1、最大子段和問題：最大子段和問題：給定由n個(gè)整數(shù)組成的序列(a1, a2, , an)（可能有負(fù)數(shù)），最大子段和問題要求該序列形如ai+aj的最大值（1ijn）。分別用蠻力法和分治法設(shè)計(jì)求解最大子段和問題，寫出算法的偽代碼描述，并分析每種方法的漸進(jìn)復(fù)雜性。 參考解答：（蠻力法） 時(shí)間復(fù)雜性：O（n2）,期末總結(jié)算法設(shè)計(jì),2、設(shè)計(jì)分治算法求一個(gè)數(shù)組中最大元素的位置，建立該算法的遞推式并求解。（課后題P74,5） 參考解答：,期

2、末總結(jié)算法設(shè)計(jì),期末總結(jié)算法設(shè)計(jì),3、在一個(gè)序列中出現(xiàn)次數(shù)最多的元素稱為眾數(shù)。請(qǐng)?jiān)O(shè)計(jì)分治算法尋找眾數(shù)并分析算法的時(shí)間復(fù)雜性。 （課后題P75,10） 參考解答（時(shí)間復(fù)雜性略）：,期末總結(jié)算法設(shè)計(jì),4、設(shè)M是一個(gè)nn的整數(shù)矩陣，其中每一行（從左到右）和每一列（從上到下）的元素都按升序排列。設(shè)計(jì)分治算法確定一個(gè)給定的整數(shù)x是否在M中，并分析算法的時(shí)間復(fù)雜性。 （課后題P75,11，算法略）,期末總結(jié)算法設(shè)計(jì),5、修改下面的折半查找算法，使其正確進(jìn)行查找。并設(shè)計(jì)寫出折半查找的遞歸形式算法，分析時(shí)間性能。（解答略） int BinSearch(int r, int n, int k) int low=

3、0, high=n-1; int mid; while(lowrmid) low=mid; else return mid; return 0; ,期末總結(jié)算法設(shè)計(jì),6、修改折半查找算法，使之能夠進(jìn)行范圍查找。所謂范圍查找是要找出在給定值a和b之間的所有元素（ab）。參考解答（復(fù)雜性分析略）：,期末總結(jié)算法設(shè)計(jì),7、請(qǐng)寫出背包問題的貪心算法偽代碼描述，并進(jìn)行時(shí)間復(fù)雜性分析。并用貪心法求解下列背包問題：有7個(gè)物品，重量分別為（2,3,5,7,1,4,1），價(jià)值分別為（10,5,15,7,6,18,3），背包容量W=15，要求寫出求解過程（P146,1）。 （參考解答略。）,期末總結(jié)算法設(shè)計(jì),8、

4、請(qǐng)寫出活動(dòng)安排問題的貪心算法偽代碼描述，并進(jìn)行時(shí)間復(fù)雜性分析。并求解下列活動(dòng)安排問題：有11個(gè)活動(dòng)等待安排，這些活動(dòng)的起止時(shí)間如下表所示，要求寫出求解過程。（參考解答略）,期末總結(jié)算法設(shè)計(jì),9、設(shè)計(jì)用回溯法求解0/1背包問題的剪枝函數(shù)，并給出相應(yīng)算法的偽代碼描述。 參考解答：,剪枝函數(shù) 設(shè)搜索至第i層，背包容量為c，當(dāng)前獲得的物品重量為cw，當(dāng)前獲得的價(jià)值為cv，當(dāng)前獲得的最大價(jià)值為bestv。 左子樹：用約束函數(shù)剪枝，當(dāng)cw+wic，則對(duì)左子樹進(jìn)行剪枝。 右子樹：設(shè)計(jì)上界函數(shù)剪枝，cp+vi+1+vnbestv，則對(duì)右子樹進(jìn)行剪枝。,主程序： 1、初始化bestv=0,cv=0,cw=0,bestx=0,0; 2、調(diào)用Backtrack(1); 3、輸出bestx1,n和bestv;,void Backtrack(int t) if(tn) if(bestvbestv) Backtrack(t+1); ,int Bound(int i) int b=cv; for(j=i;j=n;j+) b+=vj; return b; ,期末總結(jié)算法設(shè)計(jì),10、給定一個(gè)正整數(shù)集合X=x1,x2,xn和一個(gè)正整數(shù)y，設(shè)計(jì)回溯算法，求集合