这个函数复杂度高吗？

Question

我不确定以下问题：

Is log_a(n^b) in O(log_b(n^{a)) 对于常数 a, b?}

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)。

Answer 2

让我们将第一个表达式写为 b*log_a(n)，第二个表达式写为 a*log_b(n)。

第一个相当于 b*log(n)/log(a)，第二个相当于 a*log(n)/log(b)。

因此，假设是：“是否存在整数 n₀ 和 k，使得对于所有 n>n₀，b*log(n)/log(a) < ; k*a*log(n)/logb ?"

稍微简化一下，那就是：“... b/log(a) < k*a/log(b) ?”

进一步重新排列，我们有：“... b*log(b) < k*a*log(a) ?”

因此，答案取决于“a”和“b”是什么。如果 b <= a，则为“是”。