軟微B卷

五、 K路歸并，課本習(xí)題6.4

也可以用堆，時間復(fù)雜度相同六、

令子集和m=N/2，轉(zhuǎn)化為0-1背包 F[i,j]表示前i個數(shù)，和為j時使用的數(shù)字個數(shù)

狀態(tài)轉(zhuǎn)移方程： F[i,j]=max{F[i–1,j],f[i–1,j–a[i]]+1}

初始：F[0,0]=0,F[0,j]=-∞ 0<j<=m F[i,0]=0; 0<i<=n

時間復(fù)雜度O(nN)七、

貪心方案一：頻率大的在前

反例：

方案平均檢索時間：1000*0.4+

1100*0.3+1110*0.2+1111*0.1=1063.1

最少平均檢索時間：1*0.1+11*0.2+

111*0.3+1111*0.4=480

貪心方案二：文件小的在前

反例：

方案平均檢索時間：1*0.01+3*0.02+6*0.03+

10*0.94=9.65

最少平均檢索時間：4*0.94+7*0.03+9*0.02+10*0.01=4.25

貪心方案三：按fi/si從大到小排序，盡量使用單位長度頻率最大的11010010000.10.20.30.412340.010.020.030.942011年算法考題2、O(nlog2n) O(nlogn)3、n/2+n/3+n/4+…+n/(n–1) =50+33+25+20+16+14+12+11+10+9+8+7+7+6+6+5*4+4*5+3*8+2*17+1*49=3817、將數(shù)組的值排序，然后從小的數(shù)值的開始累加概率和，在第一個超過0.5的地方停止，當(dāng)前的數(shù)就是所求6、

背包可以不滿

初始：F[0,j]=0,0<=j<=T/2; F[i,0]=0,0<=i<=n

背包必須裝滿

初始：F[0,0]=0,F[0,j]=-∞ 0<j<=m F[i,0]=0; 0<i<=n初始化的f數(shù)組事實上就是在沒有任何物品可以放入背包時的合法狀態(tài)。如果要求背包恰好裝滿，那么此時只有容量為0的背包可能被價值為0的nothing“恰好裝滿”，其它容量的背包均沒有合法的解，屬于未定義的狀態(tài)，它們的值就都應(yīng)該是-∞了。如果背包并非必須被裝滿，那么任何容量的背包都有一個合法解“什么都不裝”，這個解的價值為0，所以初始時狀態(tài)的值也就全部為0了。2013年信科試題

2014年信科試題3、 n+n/2+n/4+…+

1=2n-14、

如果是絕對眾數(shù)，即出現(xiàn)次數(shù)大于等于n/2，錦標(biāo)賽法，習(xí)題2.7

否則： 1）排序，計數(shù)，時間復(fù)雜度O(nlogn)，空間復(fù)雜度O(1) 2）hash，計數(shù)，時間復(fù)雜度O(n)，空間復(fù)雜度O(n)多項式乘積的分治算法問題描述：已知多項式 P(x)=a0+a1*x+…+an*

xn Q(x)=b0+b1*x+…+bn*xn

計算P(x)*Q(x)多項式乘積的分治算法多項式乘積直接運算多項式乘法：乘法(n+1)2次，加法n*(n+1)次多項式加、減法：加、減法(n+1)次為降低時間復(fù)雜度，降階，減少乘法次數(shù)，增加加法次數(shù)，變乘為加多項式乘積的分治算法（設(shè)n為多項式系數(shù)個數(shù)）直接解：n=2時，多項式只有兩個系數(shù)，直接乘 p(x)*

q(x)=a0b0+(a0b1+a1b0)x+a1b1x2劃分：n>2時，降階，將多項式劃分為兩個多項式 p(x)=p0(x)+

p1(x)*xn/2 q(x)=q0(x)+q1(x)*xn/2多項式乘積的分治算法

多項式乘積的分治算法未降低時間復(fù)雜度的原因：使用了四次多項式乘法有效的分治算法是盡可能降低多項式乘法的次數(shù)多項式乘積的分治算法求解、組合改進：p(x)q(x)=p0(x)q0(x)+[p0(x)q1(x)+p1(x)q0(x)]xn/2+p1(x)q1(x)xn(p0(x)+p1(x))(q0(x)+q1(x))=p0(x)q0(x)+p0(x)q1(x)+p1(x)q0(x) +p1(x)q1(x)記： r0(x)=p0(x)q0(x) r1(x)=p1(x)q1(x) r2(x)=(p0(x)+p1(x))(q0(x)+q1(x))多項式乘積的分治算法

多項式乘積的分治算法例：設(shè)多項式 p(x)=1+x–x2+2x3 q(x)=1–x+2x2–3x3

用分治法求解多項式乘積的分治算法n=4,n/2=2劃分多項式得： p(x)=(1+x)+(-1+2x)x2 q(x)=(1–x)+(2–3x)x2 p(x)q(x)=r0(x)+[r2(x)-r1(x)-r0(x)]xn/2+r1(x)xn r0(x)=(1+x)(1–x)=1–x2 r1(x)=(-1+2x)(2–3x)=-2+

7x–6x2 r2(x)=(1+x–1+2x)(1–x+

2–3x)=9x–12x2多項式乘積的分治算法p(x)q(x)=r0(x)+[r2(x)-r1(x)-r0(x)]xn/