佛山科學(xué)技術(shù)學(xué)院-期末總復(fù)習(xí)-學(xué)長整理-終極版-算法設(shè)計(jì)與分析

1、遞歸與分支策略Strassen矩陣乘法是利用分治法實(shí)現(xiàn)的算法。使用分治法求解不需要滿足的條件是子問題必須是一樣的線性時(shí)間選擇算法：時(shí)間復(fù)雜度O(a)=n,時(shí)間復(fù)雜度O(11)=nlogn最接近點(diǎn)對問題算法：時(shí)間復(fù)雜度05=：遞推公式求時(shí)間復(fù)雜度的：用主定理秒殺，見算法ppt第二章，簡而言之就是a)n=logbacompaiewithf(n)i.nf(n),貝1O(n)=logbaii.n=f(n),貝1O(n)=logba*logn分治算法的基本步驟包括：分解、解決和合并動(dòng)態(tài)規(guī)劃最大子段和問題，時(shí)間復(fù)雜度為n動(dòng)態(tài)規(guī)劃法的4個(gè)步驟設(shè)計(jì)是什么？找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征遞歸地定義最優(yōu)值以自

2、底向上的方式計(jì)算出最優(yōu)值根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造矩陣連乘(M3),最長公共子序列(mn),(m+n),(minm,n),凸多邊形最優(yōu)三角剖分(n),多邊形游戲(”3),圖像壓縮(11),電路布線(M2),(11),流水作業(yè)調(diào)度(nlogii),0-1背包問題(2An),(2An,nc),最優(yōu)二叉搜索樹(M3)。動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素最優(yōu)子結(jié)構(gòu)性質(zhì)重疊子問題性質(zhì)用動(dòng)態(tài)規(guī)劃策略求解最長公共子序列問題：給出計(jì)算最優(yōu)值的遞歸方程。給定兩個(gè)序列X=B,C.D,A,Y=A,E,UE,請采用動(dòng)態(tài)規(guī)劃策略求出其最長公共子序列，要求給出過程。ioiff=()”_/=0,0and,max(c/,J-I

3、,ci一I,J)iffJ0and.i01234JYABCB0X010001B001112C0013D001214A01121最長公共子序歹I1：n)output(x);elsefor(inti=0;in)output(x);elsefor(inti=t;i近似算法九、算法優(yōu)化策略十、在線算法設(shè)計(jì)十一、其他算法由若干條指令組成的又窮序列，且滿足輸入、輸出、確定性、有限性四個(gè)特性。分支限界法的兩種搜索方式有隊(duì)列式(FIFO)分支限界法、優(yōu)先隊(duì)列式分支限界法，用一個(gè)隊(duì)列來存儲(chǔ)結(jié)點(diǎn)的表叫活節(jié)點(diǎn)表。直接或間接調(diào)用自身的方法叫遞歸算法以廣度優(yōu)先或以最小耗費(fèi)方式搜索問題解的算法稱為分支限界法動(dòng)態(tài)規(guī)劃的子問題

4、重疊貪心算法的選擇性質(zhì)是貪心選擇性質(zhì)、動(dòng)態(tài)規(guī)劃法的選擇性質(zhì)是最優(yōu)子結(jié)構(gòu)性質(zhì)。計(jì)算一個(gè)算法時(shí)間復(fù)雜度通?？梢杂?jì)算的循環(huán)次數(shù)、基本操作的頻度或計(jì)算步數(shù)&快速排序算法的性能取決于劃分的對稱性O(shè)的定義：O(g(n)=f(n)|存在正常數(shù)c和110使得對所有n=nO有：0=f(n)=nO有：0=cg(n)2簡單地說就是log底數(shù)為括號里面的倒數(shù)，真數(shù)為倍數(shù)21.22.23.24.25.26.27.有8個(gè)作業(yè)1,2,-,8要在由2臺(tái)機(jī)器Ml和M2組成的流水線上完成加工。每個(gè)作業(yè)加工的順序都是先在Ml上加工，然后在M2上加工。Ml和M2加工作業(yè)1所需的時(shí)間分別為：Ml102S1269414M25711516

5、31113作業(yè)12345678給出一個(gè)最優(yōu)調(diào)度方案，使得從第一個(gè)作業(yè)在機(jī)器Ml上開始加工，到最后一個(gè)作業(yè)在機(jī)器M2上加工完成所需的時(shí)間最少，并計(jì)算所需的最少時(shí)間。最優(yōu)調(diào)度方案為(6分)27548163所需的最少時(shí)間為：73(4分在前一問正確的前提下方可得分)28.29根據(jù)優(yōu)先隊(duì)列式分支限界法，求下圖中從vl點(diǎn)到，9點(diǎn)的單源最短路徑，請畫出求得最優(yōu)解的解空間樹。要求中間被舍棄的結(jié)點(diǎn)用X標(biāo)記，獲得中間解的結(jié)點(diǎn)用單圓30.十二、程序題合并排序mergeSoil(inta,hitleft,iiitright)if(leftright)iiiti=(left+right)/2;mergeSort(a,l

6、eft,I);mergeSort(a,i+1,light);merge(a,b,left,i,right);copv(a,b,left,light);快速排序qSoil(iiita,intp,iiiti)iiitq=parition(a,p,r);qSort(a,p,q-1);qSort(a,q+1,r)；iiitparition(inta,intp,intr)iiitstart=p,end=q;while(stailend)while(stailend&astart=aend)end;returnstart;貪心算法：背包問題voidKnapsack(intn,floatM,floatv,f

7、loatw,floatx)Sort(ii,v,w)Ult1;for(i=l;i=n;i+)xi=0;floatc=M;fbr(i=l;ic)break;xi=l；C-=W1；if(i二fj)Ai=true;Jzi：elseAi二false;動(dòng)態(tài)規(guī)劃：最大子段和intMaxSum(intn,inta)intsum=0,b=0;for(intj=l;j0)b+=aj;elseb=ai;if(bsum)sum=b;returnsum;intMaxSum(inta,intleft,intright)intsum=0;if(left=right)/序列長度為1if(aleft0)sum二aleft:el

8、seintcenter二(left+right)/2;leftsum二MaxSum(a,left,center);rightsum二MaxSum(a,center+1,right);si=0,lefts=0;for(I二center;i=left:-i)lefts+二ai:if(leftssi)si=lefts;s2=0,rights=0;for(j二center+1;j二right;+j)rights+二aj;if(rightss2)s2二rights;sum=si+s2;if(sumleftSum)sum二leftsum;if(sumrightSum)sum二rightsum;returnsum;I遞歸：全排列voidperm(Typelist,intk,intm)產(chǎn)生listk：m的所有排列if(k二二m)只剩下一個(gè)