假设一台计算机可以在时间t解决大小1000的一个问题。进一步假设这个问题有一个nlgn的复杂性。如果我们购买的可在两倍的速度运行的计算机,什么是我们能够解决在t时刻的问题的近似大小?
Suppose that a computer can solve a problem of size 1000 in time t. Suppose further that the problem has a nlgn complexity. If we purchase a computer which can run at twice the speed, what is the approximate size of the problem that we could solve in t time?
谁能告诉我答案了这一点,并解释
can anyone tell me the answer for this and the explanation
令v为初始计算机的速度。设K是新的计算机上的问题的大小。然后,我们有这样的公式:
Let v be initial computer speed. Let k be problem size on the new computer. Then we have this equation:
1000 * ln(1000) / v = k * ln(k) / (2 * v)
解决它产生钾= 1834
Solving it yields k ~= 1834