algorithm - 乘以系数的阶乘的大 Theta

Question

对于运行时间为 (cn) 的函数!其中 c 是系数 >= 0 且 c != n，运行的紧界是 Θ(n!) 还是 Θ((cn)!)？现在，我相信它会是 Θ((cn)!)，因为它们会相差一个系数 >= n，因为 cn != n。

谢谢!

编辑:一个更具体的例子来阐明我的问题:

将 (7n)!, (5n/16)!和 n!都是 Θ(n!)?

Answer 1

您可以使用 Stirling's approximation得到 if c>1 then (cn)!渐近大于 pow(c,n)*n!，它不是 O(n!)，因为商发散。作为一种更基本的方法，考虑 c=2 的这个例子:(2n)!=(2n)(2n-1)...(n+1)n!>n!n!和 (n!n!)/n!=n!发散，所以 (2n)!不是 O(n!)。