algorithm - 通过取对数比较两个复杂函数？

Question

我发现在渐近比较两个函数时取两边的对数是一种常用的技术(根据 CLRS 书中问题的一些解决方案)。

但是否总是认为两个函数取对数后的渐近关系表示它们原来的渐近关系？

我有点怀疑它在比较两个指数函数时是否有效。

例如log(3^n) = nlog3, log(2^n) = nlog2，那么应该说明O(2^n)和O(3^n)的运行时间处于同一水平，这是不对的。

Answer 1

渐近边界隐含地包含一个被忽略的乘法常数。

正式地，f(n) = O(g(n))意味着你可以找到 N和 C这样 n > N => f(n) < C.g(n) .

取对数时，乘法常数变为加法常数，log(f(n)) < log(C) + log(g(n)) ，f(n) = O(g(n)) <=> log(f(n)) = O(log(g(n))) 不是真的.

所以如果你用对数比较两个复杂度，你不能去掉一个乘法常数，而是一个加法常数，和n.Log(3)确实不同于 n.Log(2).

同样，O(n²)和 O(n³)不同是因为 2.Log(n)和 3.Log(n)没有相同的效率。