algorithm - 写[(m + n)^m] / m是否有效！作为 O([n / m]^m) 作为其宽松的上限？

Question

在写[(m + n)^m] / m!的上限时 作为O([n / m]^m)，我认为m! = O(m^m)。

Answer 1

如你所说m!。o(m^m)因此，您无法将其替换A = (m+n)^m / m!为上限！相反，您可以使用斯特林近似来获得适当的上限。正如我们所拥有的（见这里）：

m! = \sqrt{2\pi m} (m/e)^m (1 + O(1/m))

A您可以通过替换m!为来获得 的上限(m/e)^m。因此：

A < (n+m)^m / (m/e)^m = (e*(n+m)/m)^m = (e * (n/m + 1))^m

如果n > m，我们知道(n/m + 1)^m = Theta((n/m)^m)。所以，A \in O(e^m (n/m)^m)

Answer 2

它不是。

---

原因：在表达式 ((m + n) ^m ) / m! 中，值“m!” 是分母。

在小数中，增加分母会使数字变小。示例：数字 4 大于 3。因此，当放入分母时，1/4 小于 1/3 ^*。

如果是小数值，要获得更宽松的上限，您可以做两件事：

1. 增加分子；和/或，
2. 减小分母。

因为在你的近似中：

• 您正在使分母变松；所以，
• 你实际上是在增加分母；所以，
• 您正在达到较小的分数值；

借给你一个更紧密的约束，而不是一个更宽松的约束。

---

^{*这里的小学数学：将比萨饼分成四等份并得到一片与将比萨饼分成三等份并得到一大片 - 仅在 3 人之间分配时会得到更多的比萨饼。}