complexity-theory - 这个功能复杂吗？

Question

我不确定以下问题:

是 log_a(n^b) 在 O(log_b(n^a)) 中的常量一个，一个？

Answer 1

当被问及函数 f(x) 是否在 O(g(x)) 中时，它实际上比较了这两个函数的增长率。 (参见维基百科:http://en.wikipedia.org/wiki/Big_O_notation)

函数的常数因子被忽略，所以 2x 在 O(x) 中。具有较低增长率的函数组件也同样被忽略，因此 2x^2 + x + 1 在 O(x^2) 中。

所以问题是:loga n^b 的增长率是否与 logb n^a 相似？

为了解决这个问题，我们将应用对数的几个很棒的属性:

• log x^b = b log x
• loga x = (logb x)/(logb a)

首先要做的是修复我们正在比较的大 O 表示法，因为它不是最小值，通过应用上面的第一个属性我们得到:O(logb n^a) = O(a logb n) 因为从大 O 符号中删除了常数系数，所以增长率的实际表示是:O(logb n).

现在将第一个恒等式应用到我们拥有的第一个公式:

loga n^b = b loga n

接下来我们使用获得的第二个属性更改基数:

loga n^b = b (logb n)/(logb a)

这也可以组织成这样:

loga n^b = (b/logb a) logb n

请注意，(b/logb a) 是常数系数，因此 (b/logb a) logb n 的复杂度为 O(logb n)

所以这个问题的答案是肯定的。 loga n^b 在 O(logb n^a) 中。