假设某算法在输入规模为n时的计算时间为.假设某算法在输入规模为n时的计算时间为T=3*2n(2的n的次方）.在某台计算机上实现并完成该算法在t秒.现有另一台计算机,其运行速度为第一台的64倍,

Question

假设某算法在输入规模为n时的计算时间为.
假设某算法在输入规模为n时的计算时间为T=3*2n(2的n的次方）.在某台计算机上实现并完成该算法在t秒.现有另一台计算机,其运行速度为第一台的64倍,那么在这台新机器上用同一算法在t秒内能解输入输入规模为多大的问题?
请各们大侠帮帮忙?

Answer 1

某台t秒内完成的基本运算的次数=3*2^n
新机器t秒内完成的基本运算的次数=64*3*2^n=2^6*3*2^n=3*2^(n+6)
T=T(n)=3*2^n n=log2(T/3)
设新机器输入规模为n1,则：
n1=log2(3*2^(n+6)/3)=n+6
在这台新机器上用同一算法在t秒内能解输入输入规模为n+6的问题.
可见,研究算法,改进算法比提高机器速度更重要!