假设某算法在输入规模为 n 时的计算时间为 T ( n )=3nlog n 。在某台计算机上实现并完成该算法的时间为 t 秒。现有另一台计算机,其运行速度为第一台的100倍,那么在这台新计算机上用同一算法在 t 秒内能解输入规模为多大的问题?
时间: 2024-03-30 10:33:58 浏览: 13
假设在第一台计算机上,该算法在输入规模为 n 时的计算时间为 T(n) = 3nlogn,完成该算法的时间为 t 秒。
在第二台计算机上,运行速度为第一台的100倍,因此该算法在第二台计算机上的时间为 t/100 秒。
设在第二台计算机上,用同一算法能够解决的最大输入规模为 m,则该算法在第二台计算机上的计算时间为 T(m) = 3mlogm。
因为第二台计算机的运行速度是第一台的100倍,所以有:
T(m) / T(n) = (3mlogm) / (3nlogn) = mlogm / nlogn = 100
解得:
m = 100n
因此,用同一算法在第二台计算机上能够解决的最大输入规模是第一台计算机上的100倍,即输入规模为 100n。
相关问题
假设某算法在输入规模为 n 时的计算时间为 T ( n )=3nlog n 。在某台计算机上实现并完成该算法的时间为 t 秒。现有另一台计算机,其运行速度为第一台的100倍,那么在这台新计算机上用同一算法在 t 秒内能解输入规模
为多少?
首先,我们可以通过输入规模为 n 时的计算时间 T(n) = 3nlogn 求出输入规模为 n 时的计算时间复杂度为 O(nlogn)。
接着,我们可以通过原先计算机的时间 t 和输入规模为 n 的计算时间 T(n) 推导出原先计算机能够处理的最大输入规模为:
t = 3nlogn
n = (t / 3) / logn
然后,我们可以根据新计算机的速度是原计算机的100倍,推导出新计算机能够处理的最大输入规模为:
n' = n * 100
= ((t / 3) / logn) * 100
≈ 210n
因此,在新计算机上用同一算法在 t 秒内能解输入规模为约为 210n 的问题。
t(n)= n3 +O(nlog²n) 时间复杂度
分析。
很高兴回答你的问题。根据时间复杂度的定义,t(n)= n3 O(nlog²n) 表示 t(n) 增长的上界是 n3 乘以一个关于 nlog²n 的常数,即 t(n) 的增长速度小于等于 n3 乘以 O(nlog²n)。因此,时间复杂度可以表示为 O(n3log²n)。希望我的回答能够帮助你。