将 [(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{2pi m} (m/e)^m (1 + O(1/m))

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

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. 减小分母。

由于在您的近似值中：

• 你使分母更松;因此，
• 你实际上是在增加分母;因此，
• 您正在达到较小的分数值;

借给你一个更紧的界限，而不是更宽松的束缚。

---

^{*这里的小学数学：将披萨分成四个相等的部分，得到一片，vs 将披萨分成三个相等的部分，得到一大片 - 当只在3个人之间分配时，你会得到更多的披萨。}