算法期末复习重点及答案.doc

《算法期末复习重点及答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.假设某算法在输入规模为n时的计算时间为T(n)=3*2n,在某台计算机上实现并完成该算法的时间为t秒。现有另一台计算机，其运行速度是第一台的64倍，那么在新机器上用同一算法在t秒内能解输入规模为多大的问题。2.若上述算法的计算时间改进为t(n)=n2,其余条件不变，则新机器上用t秒能解问题的规模。3.若上述算法的计算时间改进为t(n)=8,其余条件不变，则新机器上用t秒能解问题的规模。nN+6n8*nn任意规模6¨61到n平方的累加和¨2）基本语句：s=s+i*i；¨3）执行次数：n次¨4）效率类型：时间复杂度为线性阶¨5）利用数学公式进行改进：s=n*(n+1)*(

2、2*n+1)/6n时间效率为O（1）7¨）¨T(n)=3T(n-1)¨=3(3T(n-2))=32*T(n-2)¨=……¨=3kT(n-k)¨设n-k=1，则k=n-1¨T(n)=3n-1*T(1)=4*3n-1=O（3n）8¨8.IntQ(intn)¨{§If(n==1)return1;§ElsereturnQ(n-1)+2*n-1;¨}n1)求n2n2)n=3Q(3)=Q(2)+2*3-1n=（Q(1)+2*2-1）+5n=（1+4-1）+5=9n3）Q(n)=Q(n-1)+2*n-1n=(Q(n-2)+(2*(n-1)-1)）+2*n-1=Q(n-2)+2(2n-2

3、)n=Q(n-3)+3(2n-3)=….=Q(n-k)+k(2n-k)n设n-k=1则k=n-1nQ(n)=1+(n-1)(2n-n+1)=1+n2-1=n2n4)非递归算法:returnn*n;