了解上限、下限算法分析的实例

Question

我正在继续理解渐近分析的任务。如果 mods 愿意，最好只有一个元 post。不管怎样：

我有两个功能：

 f(n) = n^2
 g(n) = (log n)^80

根据 l'Hopitals 规则分析：

 lim(n->∞) f(n)/g(n) = f'(n)/g'(n)

这给我们留下了：

 f'(n)/g'(n) = 2n/(80*(log n / √2)

这最终将导致我们：

 0/g''(n) = 0

据我了解，这表明 f(n) = o(g(n))

我的理解正确吗？

Answer 1

如果分子和分母都收敛于零或无穷大，则可以应用 L'Hopital 规则。所以你的方法在一般情况下是正确的。但是你在计算 g'(n) 时犯了错误。

g'(n) = (80 * log(n)) * 1/(2 ln (n))
  => f'(n)/g'(n) = 2n / ((80 * log(n)^79) * 1/(n ln(2))) 
   = 2n^2 / 80log(n)^79 ln(2)

此时f'(n)/g'(n)的极限也是∞/∞。所以你可以再次应用 L'Hopital 规则。但结果是一样的。但是在第 80 次申请之后，你有这个：

2^80 n^2 / 80! ln(2)^80
  =>  lim(n->∞) f(n)/g(n) = ∞

因此，g(n) = o(f(n)).

Understanding an instance of upper bound, lower bound algorithmic analysis