algorithm - 家庭作业帮助 - 复杂性和运行时间

Question

我知道这是一个简单的问题，但请耐心等待。我得到了一些复杂的算法(log(n)、sqrt(n)、n、...)，我需要找到可以在指定时间(1 秒、1 分钟、 1小时， ...)。说明还说“......假设算法，解决问题需要 f(n) 微秒)”。任何人都可以帮助我开始吗？我已经有了解决方案，我只是不知道如何计算它。

log(n) => 的解决方案

1 second = 2^(10^6)

1 minute = 2^(6 * 10^7)

1 hour = 2^(3.6 * 10^9)

Answer 1

虽然这是一项可怕的练习，但实际上非常简单。给你一个函数 f(n)以及该函数的值。例如，1 秒表示 10^6 微秒。所以基本上你被要求解决n对于以下等式:

• f(n) = 10^6 , 因为 10^6us 是 1 秒
• f(n) = 60 * 10^6 , 因为 60 秒是 1 分钟
• f(n) = 3600 * 10^6 , 因为 3600 秒是 1 小时

在你的例子中 f(n)是log(n) .简短的回答是，如果你有 f(n) = k , 然后找到 n你需要 f 的反函数.换句话说，n = f<sup>-1</sup>(k) .

对于 f(n) = log(n) , f<sup>-1</sup>(n) = 2^n .

您现在应该能够自己找出联系并为其他人解决您的作业 f(n)