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

Question

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

Answer 1

示例： d = 2

f(2) = 4, f(3) = 9, f(4) = 16 ....

对于： d = 3

f(2) = 8, f(3) = 21, f(4) = 64 ... . . .

所以只要n>1（你说的是b，其实是n）且d为正数时间复杂度为 O(n^d)

这里也可以看到函数的增长是什么

Answer 2

让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，当b>1时，我们可以说n^d=O(b^n)（O的另一种定义是https://en.wikipedia.org/wiki/Big_O_notation）。

要点是 exponential 函数比 polynomials 增长得更快。

Answer 3

我想我想出了一个替代@Sandipan Dey 的解决方案。由于 b > 1 且 d > 0，b ^ ( 1 / d ) > 1。因此，log_b^(1/d)(n ) < 名词。由此可见，

  => log n / log (b^(1/d)) < n
  => d*logn < d*n*log (b^(1/d))
  => log (n^d) < log (b^((1/d)*n*d)))
  => n^d <= b^n

证明n^d是O(b^n)的。

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

Why is the complexity of the function f(n) = n^d, O(b^n), where b>1 and d is positive?

algorithm

complexity-theory