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

Closed. This question does not meet Stack Overflow guidelines。它当前不接受答案。












想改善这个问题吗？更新问题，以便将其作为on-topic用于堆栈溢出。

9个月前关闭。



Improve this question




在写 [(m + n)^ m] / m的上限时! 为 O([n / m] ^ 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))

通过将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)