math - CLRS 练习 3.2-4 Big-Oh vs Little Oh

Question

我正在自学 CLRS，我已经达到了这一点——我要回答的问题是：

Is the function ⌈lglgn⌉! polynomially bounded?

我把它减少到

=Θ(lglgn⋅lglglgn)

现在，在这一点上，所有解决方案手册似乎都很少使用哦

=o(lglgn⋅lglgn)

这一步让我有点困惑；我以为我理解的很少——哦，但显然不够好——有人可以在这个特定的背景下框架它吗？接下来的步骤也从

=o(lg^2 n)

至

=o(lgn)

这仅仅是L'hopitals规则的应用吗？

Answer 1

如果你有一个渐近等价于lglgn⋅lglglgn（所以它在 中Θ(lglgn⋅lglglgn)）的函数，那么lglgn⋅lglgn是一个上限，因为lglglgn在 中o(lglgn)。

我不确定最后一步：

• 如果o(lg^2 n)意味着o((lg n)^2)，你不能说它在o(lg n)。这是错误的。
• 如果o(lg^2 n)意味着o(lglg n)，这只是切换到更大的上限，因为lglg nis in o(ln n)。