理解上限，下界算法分析的实例

Question

我将继续完成理解渐近分析的任务。如果mod更喜欢，最好只有一个元帖子。无论如何：

我有两个功能：

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

从l'Hopital规则的分析：

 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））。