n 日志 n 和计算机速度

Question

假设一台计算机可以在时间t中解决大小为1000的问题。 进一步假设该问题具有 nlgn 复杂性。如果我们购买一台可以以两倍速度运行的计算机，那么我们可以在t时间内解决的问题的大致大小是多少？

谁能告诉我这个的答案和解释

Answer 1

设 v 为初始计算机速度。让 k 成为新计算机上的问题大小。然后我们有这个等式：

1000 * ln(1000) / v = k * ln(k) / (2 * v)

求解得到k ~= 1834