algorithm - 为什么lgn和log8n的渐近关系等价于logn为Θ(log8n)？

Question

我正在尝试理解以下问题的正确答案:

screen shot of question

答案都是正确的，因为 lgn 可以说是 log8n 的 theta，它包括所有三个选项。

这让我感到困惑，因为对于 n 的任何正值，logn 都会大于 log8n，对吗？说 logn 与 log8n 紧密绑定(bind)意味着 logn 既是 log8n 的 Big O 又是 log8n 的 Big Omega。或者用简单的英语来说，logn 不大于 k1 x log8n 且不小于 k2 x log8n。

我的回答是 logn 是 log8n 的 Big Omega，因为它永远不会花费更少的时间。为什么这是错误的？

Answer 1

假设 lg 表示自然对数，则有 log_8(n)=lg(n)/lg(8) 因此这两个函数的区别仅在于乘法因素。

现在，让我们检查一下来自 this table 的 Big O 案例，其中 f 是 lg 而 g 代表 log_8。如果我们设置k=lg(8)，那么第三列的条件就自动满足了。换句话说，条件“|f| 受 g 限制(直到常数因子)”得到满足，因为从宽泛的角度来说，这两个函数实际上是相同的直到常数(乘法)因子。

同样的推理适用于 Big Omega，因此也可以获得 Big Theta(您可以直接使用 k1=k2=lg(8) 在其定义中)