algorithm - 计算可以在一定时间内解决的大小 N

Question

我正在做一个练习(注意没有家庭作业问题)，其中给出了计算机可以练习的一些步骤，并且要求一个人计算与某些时间间隔相关的多个函数的 N。

我对 f(n) = n, n^2, n^3 等函数执行此操作没有问题。

但是当谈到 f(n) = lgn, sqrt(n), n log n, 2^n, and n! 时，我遇到了问题。

我很清楚，我必须构造一个 func(n) = interval 形式的项，然后必须得到 n。

但是如何使用上面的函数来做到这一点呢？

谁能给我一个例子，或者说出反函数的名字，以便我可以在维基百科或其他地方查找。

Answer 1

您的问题与其说是关于算法或复杂性，不如说是关于数学公式的求逆。

n^k = N 中的n 很容易以封闭形式求解。不幸的是，对于大多数其他功能，它要么是未知的，要么是已知的，这是不可能的。特别是，对于 n log(n)，解决方案 involves the Lambert function ，这对你没有多大帮助。

在大多数情况下，您必须用数字来解决这类问题。