CLRS练习3.2-4大-哦对小哦

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 n在o(ln n)中。