假设某算法在输入规模为 n 时的计算时间为 T ( n )=3nlog n 。在某台计算机上实现并完成该算法的时间为 t 秒。现有另一台计算机，其运行速度为第一台的100倍，那么在这台新计算机上用同一算法在 t 秒内能解输入规模为多大的问题？

假设在原先的计算机上，输入规模为n时，算法的运行时间为T(n) = 3nlogn。那么在该计算机上运行时间为t的情况下，我们可以求出其能够处理的最大输入规模：

t = 3nlogn

n = t / (3logn)

现在，我们考虑在新的计算机上运行该算法，该计算机的速度是原先计算机的100倍。由于算法的时间复杂度是O(nlogn)，因此在新计算机上运行该算法时的时间复杂度与在原先计算机上运行该算法时的时间复杂度相同，仍然是O(nlogn)。但是，由于新计算机的速度是原先计算机的100倍，因此新计算机能够处理的输入规模是原先计算机能够处理的输入规模的100倍。因此，在新计算机上用同一算法在t秒内能够解决的问题规模为：

n' = 100 * n = 100 * (t / (3logn)) ≈ 33.22t

因此，在新计算机上用同一算法在t秒内能够解决输入规模约为33.22t的问题。

相关问题

假设某算法在输入规模为 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)。希望我的回答能够帮助你。