algorithm - 为什么函数的复杂度是 f(n) = n^d, O(b^n)，其中 b>1 且 d 为正数？

Question

所以，我在我的离散数学书中遇到了这个问题，它说，函数 f(n) = n^d 的复杂度是 O(b^n) ，其中 b>1 和 d 为正数。但我似乎无法理解为什么。任何帮助将不胜感激。

Answer 1

让L = lim{n->inf} (n^d/b^n)
=> ln(L) = lim{n->inf} (d*ln(n) / (n*ln(b)))
= (d/ln(b)) * lim{n->inf} (ln(n) / n) = (inf) / (inf)
= (d/ln(b)) * lim{n->inf} (d/dn(ln(n)) / d/dn(n)) (申请L-Hospital)

      = (d/ln(b)) * lim{n->inf} (1/n) / (1) = (d/ln(b)) * 0 = 0 

(自 b>1 ， ln(b) > 0 )

=> L = exp(0) = 1 < inf

自 lim{n->inf} (n^d/b^n) < inf ，我们可以说 n^d=O(b^n)什么时候b>1 (请参阅此以了解 O 的替代定义:https://en.wikipedia.org/wiki/Big_O_notation)。

要点是 exponential函数增长速度快于 polynomials .