我遇到了两个渐近函数证明。
f(n) = O(g(n)) 意味着 2^f(n) = O(2^g(n))
Given: f(n) ≤ C1 g(n)
So, 2^f(n) ≤ 2^C1 g(n) --(i)
Now, 2^f(n) = O(2^g(n)) → 2^f(n) ≤ C2 2^g(n) --(ii)
From,(i) we find that (ii) will be true.
Hence 2^f(n) = O(2^g(n)) is TRUE.
你能告诉我这个证明是否正确吗？有没有其他方法可以解决这个问题？
2.f(n) = O((f(n))^2)
如何证明第二个例子？这里我考虑两种情况，一种是 f(n)<1，另一种是 f(n)>1。
Note: None of them are homework questions.
示例 1 的尝试证明看起来是善意的，但存在缺陷。首先，“<code>2^f(n) ≤ 2^C1 g(n)”的意思是2^f(n) ≤ (2^C1)*g(n)，一般来说是假的。应该是这样写2^f(n) ≤ 2^(C1*g(n))的。在以“现在”开头的那一行，你应该明确地说C2 = 2^C1。声称“（ii）将是真实的”是空洞的（没有（ii））。
类似的函数f(n) = 1/n反驳了示例 2 中的主张，因为没有常数 N 和 C 使得对于所有 n > N，f(n) < C*(f(n))²。证明：给定一些 N 和 C。选择 n>N，n>C。f(n) = 1/n = n*(1/n²) > C*(1/n²) = C*(f(n))²。因为 N 和 C 是任意选择的，这表明没有 N 和 C 的固定值，使得对于所有 n > N，f(n) < C*(f(n))²，QED。
说“f(n) ≥ 1”不足以证明第二个主张；但如果你写“f(n) ≥ 1 for all n”或“f() ≥ 1”，这是可证明的。例如，如果奇数 n 为 f(n) = 1/n，偶数 n 为 1+n，则偶数 n > 0 时 f(n) > 1，奇数 n 时 f(n) > 1。要证明 f(n) = O((f(n))²) 为假，请使用与上一段相同的证明，但附加规定 n 是偶数。
实际上，“f(n) ≥ 1 for all n”比确保 f(n) = O((f(n))²) 所必需的要强。令 ε 为任何固定的正值。不管 ε 有多小，“f(n) ≥ ε for all n > N'”确保 f(n) = O((f(n))²)。为了证明这一点，取 C = max(1, 1/ε) 和 N=N'。