这种确定上限的推理有什么问题？
What is wrong with this reasoning to determine the upper bound?
算法给了我一道题class
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 的上限，所以它与上面更明显的说法相矛盾。我在这个推理中做错了什么？
从本质上讲，您的推理可以归结为以下陈述：
If log f(n) ≤ c log g(n) for some constant c, then f(n) = O(g(n)).
不过，这种说法通常不是真的。看到这一点的一种方法是找到一些反例：
如果 f(n) = n4 且 g(n) = n，则 log f(n) = 4 log n 和 log g( n) = 日志 n。确实存在大于 4 log n 的 log n 的倍数，但是 n4 ≠ O(n).
如果 f(n) = 4n 且 g(n) = 2n，则记录 f (n) = 2n 和 log g(n) = n。有一个 n 的倍数使它大于 2n，但是 4n ≠ O(2n).
要真正了解为什么这不起作用，请注意 c log g(n) = log g(n)c，因此将 log 乘以常数是相当于将原始函数提高到某个大的幂。你可以通过将一个函数乘以一个常数来推断它的 big-O，但是你不能通过将它提高到某个幂来推断它，这就是为什么这个推理会失败。
算法给了我一道题class
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 的上限，所以它与上面更明显的说法相矛盾。我在这个推理中做错了什么？
从本质上讲，您的推理可以归结为以下陈述：
If log f(n) ≤ c log g(n) for some constant c, then f(n) = O(g(n)).
不过，这种说法通常不是真的。看到这一点的一种方法是找到一些反例：
如果 f(n) = n4 且 g(n) = n，则 log f(n) = 4 log n 和 log g( n) = 日志 n。确实存在大于 4 log n 的 log n 的倍数，但是 n4 ≠ O(n).
如果 f(n) = 4n 且 g(n) = 2n，则记录 f (n) = 2n 和 log g(n) = n。有一个 n 的倍数使它大于 2n，但是 4n ≠ O(2n).
要真正了解为什么这不起作用，请注意 c log g(n) = log g(n)c，因此将 log 乘以常数是相当于将原始函数提高到某个大的幂。你可以通过将一个函数乘以一个常数来推断它的 big-O，但是你不能通过将它提高到某个幂来推断它，这就是为什么这个推理会失败。