O((log n)!) 是多项式吗？
Is O((log n)!) polynomial?
我想找到 O((log n)!)。我认为 O((log n)!) 和 O(n!) 是相等的！因为我认为当 n 是无穷大时 (log n)! 和 n! 是相等的。是真的吗？如果是，我该如何证明？如果不是 O((log n)!) 多项式？
让我们回到一些基础数学：
我们知道如果 log a > log b, then a>b :(log base is greater than 1)
click here to get more on this
现在我们知道 log(N!)=NLogN (see here for proof)
并持有相同的参数，我们得到，log((log N)!)=logN logLogN
因为，
log(N!) 是多项式次数，log((log N)!) 是对数阶的，
清楚地，
O(N!) >O((logN)!)
希望这有帮助。
通过使用 Stirling's approximation 说明 $ n! ~ \sqrt{2 \pi n} \frac{n}{e}^n (1 + O(frac{1}{n})) $，并对 $ \log{n} $ 使用相同的公式，一个可以检查 $ n! $ 主导因素是 $ n ^ n $ 而对于 $ \log{n}! $ 相同的因子变为 $ \log{n} ^ \log{n} $。通过使用 $ \ln{n} \leq n - 1 $ 这一事实，我相信您可以轻松证明 $ O(\log{n}!) $ 小于 $ O(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
, 而 e^200≈1086
既然已经完成了适当的数学运算，让我添加一个更直观的解释，说明为什么给定的 c 为 O(log(n)!) > O(n^c)。我们假设对数以 2 为底，为简单起见，选择 c 作为 10。（该论证适用于不同数量的一般值）。
那么，为什么 log(n)! 会变得比 n^10 更大？让我们来看看这两个函数在 2 的幂处的值，更具体地说，与最后一个 2 的幂相比它们增长了多少。（n = 2^p 从现在开始）
log(2^p)! = p * log(2^(p-1))!、(2^p)^10 = 2^10 * (2^(p-1))^10。这可能看起来很复杂，但它告诉我们 log(n)! 函数会将其值乘以 2 的每个 p 次方乘以 p，但 n^10 将仅将其值乘以 1024，因此 log(n)! 最终会变得越来越大。
此外，log(n)! 比任何指数增长都慢，类似的论点可以通过观察当 n 增长 1 时两个函数乘以它们的值来得出。
我想找到 O((log n)!)。我认为 O((log n)!) 和 O(n!) 是相等的！因为我认为当 n 是无穷大时 (log n)! 和 n! 是相等的。是真的吗？如果是，我该如何证明？如果不是 O((log n)!) 多项式？
让我们回到一些基础数学：
我们知道如果 log a > log b, then a>b :(log base is greater than 1)
click here to get more on this
现在我们知道 log(N!)=NLogN (see here for proof)
并持有相同的参数，我们得到，log((log N)!)=logN logLogN
因为，
log(N!) 是多项式次数，log((log N)!) 是对数阶的，
清楚地，
O(N!) >O((logN)!)
希望这有帮助。
通过使用 Stirling's approximation 说明 $ n! ~ \sqrt{2 \pi n} \frac{n}{e}^n (1 + O(frac{1}{n})) $，并对 $ \log{n} $ 使用相同的公式，一个可以检查 $ n! $ 主导因素是 $ n ^ n $ 而对于 $ \log{n}! $ 相同的因子变为 $ \log{n} ^ \log{n} $。通过使用 $ \ln{n} \leq n - 1 $ 这一事实，我相信您可以轻松证明 $ O(\log{n}!) $ 小于 $ O(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
, 而 e^200≈1086
既然已经完成了适当的数学运算，让我添加一个更直观的解释，说明为什么给定的 c 为 O(log(n)!) > O(n^c)。我们假设对数以 2 为底，为简单起见，选择 c 作为 10。（该论证适用于不同数量的一般值）。
那么，为什么 log(n)! 会变得比 n^10 更大？让我们来看看这两个函数在 2 的幂处的值，更具体地说，与最后一个 2 的幂相比它们增长了多少。（n = 2^p 从现在开始）
log(2^p)! = p * log(2^(p-1))!、(2^p)^10 = 2^10 * (2^(p-1))^10。这可能看起来很复杂，但它告诉我们 log(n)! 函数会将其值乘以 2 的每个 p 次方乘以 p，但 n^10 将仅将其值乘以 1024，因此 log(n)! 最终会变得越来越大。
此外，log(n)! 比任何指数增长都慢，类似的论点可以通过观察当 n 增长 1 时两个函数乘以它们的值来得出。