algorithm - 这种确定上限的推理有什么问题？

Question

我在算法课上出了一道题

is 2^{2n} upper bounded by  O(3^n)?

现在清楚 2^2n 是 4^n，并且 4^n 不能是 3^n 的上界。

但是如果我在两边都记录

On LHS I get 2n
On RHS I get kn (where k is some constant)

2n 的上限可以是 kn，所以它与上面更明显的说法相矛盾。我在这个推理中做错了什么？

Answer 1

从本质上讲，您的推理可以归结为以下陈述:

If log f(n) ≤ c log g(n) for some constant c, then f(n) = O(g(n)).

不过，此声明通常不是真实的声明。看到这一点的一种方法是找到一些反例:

• 如果 f(n) = n⁴ 且 g(n) = n，则 log f(n) = 4 log n 和 log g(n) = log n。确实存在大于 4 log n 的 log n 的倍数，但 n⁴ ≠ O(n)。

• 如果 f(n) = 4ⁿ 且 g(n) = 2ⁿ，则记录 f(n) = 2n 并记录 g(n ) = ñ。有一个 n 的倍数使它大于 2n，但是 4ⁿ ≠ O(2ⁿ)。

要真正了解为什么这不起作用，请注意 c log g(n) = log g(n)^c，因此将 log 乘以常数等同于提高原始值对一些大功率起作用。您可以通过将一个函数乘以一个常数来推断它的大 O，但您不能通过将它提升到某个幂来推断它，这就是为什么这种推理会失败。