我想找到O((log n)!)。我认为O((log n)!)和O(n!)是相等的！因为我认为当n是无穷大时(log n)!和n!是相等的。是真的吗？如果是的话，我怎么能证明如果不是O((log n)!)多项式？
最佳答案
我认为你的后续问题是(logn)!是否是多项式有界的。它显然不是多项式本身。斯特灵的近似给了我们n!≤en^[n+1/2]*e^(−n)
所以，(log n)!≤e(log n)^[1/2+log n]*e^(−log n)
现在(log n)^log n=(e^loglogn)^logn=e^[(logn)⋅(loglogn)]
所以，生长的顺序大约是e^[(logn)(loglogn)−logn] =n^[(loglogn)−1]
不幸的是，这不受任何多项式的限制，因为loglogn最终将超过任何正整数。
例如，将(log n)!与n^2进行比较。
当n=e^10,(log n)!=3480时
在(e^10)2≈4.85×108
，而n=e^100,(log n)!≈10157