algorithm - 我们有一个非阶乘函数 Θ(n!) 吗？

Question

所以我知道 f(n)=n^n 与 g(n)=n! 和 t(n) 相比有更大的增长=2^n 增长较少

但我找不到任何与 n 具有相同顺序的函数!并且不是阶乘函数

我们有这样一个函数，它是 Θ(n!) 并且不是阶乘的吗？如果我们有这样的功能，您能举几个吗？

Answer 1

是的 - 最著名的之一 asymptotic equivalent n! 由其 Stirling's approximation 给出，即:

(1)  n! ~ sqrt(2.pi.n).(n/e)^n

注意等价的使用，它比Θ关系强。前者暗示后者:

(2)  f(n) ~ g(n) => f(n) = Θ(g(n))

通过 (1) 和 (2) 你得到:

n! = Θ(sqrt(2.pi.n).(n/e)^n)

由于您要求的是 Θ 近似而不是等价，因此您可以创建任意数量的函数，例如乘以 2 - sin(n)(这不是特别有用!):

n! = Θ((2 - sin(n)).sqrt(2.pi.n).(n/e)^n)