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

1.假设某算法在输入规模为n时的计算时间为T(n)=3*2n,在某台计算机上实现并完成该算法的时间为t秒现有另一台计算机其运行速度是第一台的64倍那么在新机器上用同一算法在t秒内能解输入规模为多大的问题 2.若上述算法的计算时间改进为t(n)=n2,其余条件不变则新机器上用t秒能解问题的规模 3. 若上述算法的计算时间改进为t(n)=8,其余条件不变则新机器上用t秒能解问题的规模 N+6 8*n