O(n!) 与 O((n+1)!) 相同吗？

Question

因为 O(n²) 与 O((n+k)²) 相同，其中 k 是任何常数。那么上面的说法是否也符合同样的逻辑呢？

例如： O((n+1)²) => O(n² + n + 1) => O(n ²)

Answer 1

没有。 O((n+1)!) 是 O((n+1)n!)，因此 O(n) 比 O(n!) 大。

转到大 O 符号的定义，

没有常量 c

(n+1)! <= c*n!

适用于任意大的 n。

Answer 2

参考Big O notation的定义。当且仅当：

时，这些函数在 Big O 意义上才被认为是相等的

存在一个常量M，使得：

|(n+1)!| < M |n!|

在对这个不等式进行简单的数学简化后，你得到：

(n+1)! / n! < M

最后：

n+1 < M

对所有 n 来说都是这样，对某些 M 来说是这样吗？ 不 - 您可以看到，对于您选择的任何 M，都会有一些 n 的值（例如，您始终可以选择 n = M - 1），但这是不正确的。因此，O((n+1)!) 与 O(n!) 不同。

正如 Nils Pipenbrinck 所指出的，在实践中这并不重要，因为 类 这两个问题对于 n.

的实际值来说都不容易处理