algorithm - 计算 nlog(n) 和 n! 当时间为 1 秒时。（算法需要 f(n) 微秒）

Question

鉴于 CLRS 算法书中的以下问题。

对于下表中的每个函数 f(n) 和时间 t，确定在时间 t 可以解决的问题的最大大小 n，假设解决问题的算法需要 f(n) 微秒。

1. 当时间为 1 秒时，如何计算 f(n)=nlog(n) 的 n？
2. 对于 f(n)=n，如何计算 n！什么时候是1秒？

Answer 1

提到该算法需要 f(n) 微秒。然后，可以认为该算法由 f(n) 个步骤组成，每个步骤需要 1 微秒。

给出的问题表明相关的 f(n) 值受 1 秒的限制。（即 10 ⁶微秒）然后，由于您正在寻找满足这些条件的最大 n ，因此您的问题归结为下面给出的不等式。

1) f(n) = nlog(n) <= 10 ⁶

2) f(n) = n! <= 10 ⁶

我相信其余的主要是用代数和对数方程来寻找相关值。

Answer 2

在第一种情况下，您可以参考牛顿法示例计算立方根牛顿法逼近根或兰伯特 W 函数。它可能有助于计算 n 的值。根据我的发现，大多数情况下没有其他分析方法可以提供帮助。

在第二种情况下，python 脚本可以帮助手动计算 n。

def calFact(n):
    if(n == 0 or n==1):
        return n
    return n*calFact(n-1)

nVal=1
while(calFact(nVal)<1000000):         # f(n) = n! * 10^-6 sec
    nVal=nVal+1                       # 10^6 = n!

print(nVal)

所以在这种情况下，我们试图找出 n 使得 n! 等于或接近 10^6。