CLRS 练习 3.2-4 Big-Oh vs Little Oh
CLRS exercise 3.2-4 Big-Oh vs Little Oh
我正在自学CLRS，遇到了这个问题——我要回答的问题是：
Is the function ⌈lglgn⌉! polynomially bounded?
我已经将它减少到
=Θ(lglgn⋅lglglgn)
现在，所有的解决方案手册在这一点上似乎都很少用到
=o(lglgn⋅lglgn)
这一步让我有点困惑；我以为我理解得很少——哦，但显然还不够——有人可以在这个特定的上下文中构建它吗？此外，接下来的步骤来自
=o(lg^2 n)
到
=o(lgn)
这仅仅是 L'hopitals 规则的应用吗？
如果你有一个渐近等价于 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). 中
我正在自学CLRS，遇到了这个问题——我要回答的问题是：
Is the function ⌈lglgn⌉! polynomially bounded?
我已经将它减少到
=Θ(lglgn⋅lglglgn)
现在，所有的解决方案手册在这一点上似乎都很少用到
=o(lglgn⋅lglgn)
这一步让我有点困惑；我以为我理解得很少——哦，但显然还不够——有人可以在这个特定的上下文中构建它吗？此外，接下来的步骤来自
=o(lg^2 n)
到
=o(lgn)
这仅仅是 L'hopitals 规则的应用吗？
如果你有一个渐近等价于 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). 中