math - 如何证明这个大 O 符号的陈述？

Question

如何证明:

1. 4ⁿ = O(8ⁿ)
2. 8ⁿ = O(4ⁿ)？

那么这两种情况的 C 和 n0 值是多少？

Answer 1

编辑:我试图澄清我更多...

1.为了证明(参见 formal definition of Big-O)，我们必须找到任何 C 和 n0，即 4ⁿ <= C * 8 ⁿ 对所有 n > n0。所以 - 为了证明你的情况 1 就是为这两个值找到一个例子。我们将尝试......我刚刚从维基百科引用的等式说:

f(n) = O(g(n))

当且仅当存在正实数 C 和实数 n0 时

|f(n)| <= C * |g(n)| for all n > n0

其中 f(n) = 4ⁿ 且 g(n)=8ⁿ

4^n    <= C * 8^n
4^n    <= C * 2^n * 4^n
1      <= C * 2^n

所以我们选择C为1，n0也为1。等式成立 -> 案例 1 已证明。

2。因为我猜，这是家庭作业 - 你应该自己试一试 - 只要你提供自己尝试的结果，我可以帮助你更多。
提示:尝试在那里也找到一个 C 和一个 n0 - 也许你可以证明，永远不存在任何一对 C 和n0 用于等式 ... ^^