N日志N和计算机的速度 [英] n log n and computer speed

问题描述

假设一台计算机可以在时间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

这篇关于N日志N和计算机的速度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！