<分区>
在将 [(m + n)^m]/m! 的上限写为 O([n/m]^m) 时，我考虑过那个米! = O(m^m) .
<分区>
在将 [(m + n)^m]/m! 的上限写为 O([n/m]^m) 时，我考虑过那个米! = O(m^m) .
最佳答案
正如您所说，m! 是 o(m^m)。因此，您无法在 A = (m+n)^m/m! 中替换它以获得上限!相反，您可以使用斯特林近似值来获得适当的上限。正如我们所拥有的(参见 here ):
m! = \sqrt{2\pi 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)
关于algorithm - 写成[(m + n)^m]/m有效吗!作为 O([n/m]^m) 作为其宽松的上限？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/59155616/