)假设某算法在输入规模为n时的计算时间为T(n)=4*2^n。在某台计算机上实现并完成该算法的时间为t秒。现有另一台计算机,其运行速度为第一台的25倍,那么在这台新的机器上用同一算法在t秒内能解输入规模为多大的问题? 2)若上述算法的计算时间改进为T(n)=n^2,其余条件不变,则在新的机器上用t秒时间能解输入规模为多大的问题? 3)若上述算法的计算时间改进为T(n)=20,其余条件不变,则在新的机器上用t秒时间能解输入规模为多大的问题?
时间: 2023-03-23 10:03:05 浏览: 146
1) 对于假设某算法在输入规模为n时的计算时间为T(n)=4*2^n,若在某台计算机上实现并完成该算法所需时间为t秒。现在有另一台计算机,其运行速度是第一台计算机的25倍,那么在这台新机器上用相同的算法解决该问题需要多长时间?
答案:假设第一台计算机用t秒完成算法,则该算法在第二台计算机上所需的时间为:t/25秒。因为第二台计算机的运行速度是第一台计算机的25倍,所以它可以在第一台计算机所需的时间的1/25内完成同样的工作。
2) 如果假设在上述问题中,算法的计算时间改为T(n)=n^2,除此之外条件不变,那么在新的计算机上用相同的算法解决该问题需要多长时间?
答案:如果算法的计算时间为T(n)=n^2,则在第一台计算机上完成算法所需的时间为T(n)=n^2。现在假设在第二台计算机上使用相同的算法,则该算法在第二台计算机上所需的时间为:(n/5)^2。因为第二台计算机的速度是第一台计算机的25倍,所以它需要的时间是第一台计算机所需的1/25。所以 (n/5)^2 * (1/25) = n^2 * (1/25),即第二台计算机用的时间是第一台计算机的1/25。
3) 如果假设在上述问题中,算法的计算时间改为T(n)=20,除此之外条件不变,那么在新的计算机上用相同的算法解决该问题需要多长时间?
答案:如果算法的计算时间为T(n)=20,则在第一台计算机上完成算法所需的时间为T(n)=20。现在假设在第二台计算机上使用相同的算法,则该算法在第二台计算机上所需的时间为:20/25 = 0.8秒。因为第二台计算机的速度是第一台计算机的25倍,所以它需要的时间是第一台计算机所需的1/25。因此,在第二台计算机上用相同的算法解决该问题只需要0.8秒的时间。