使用大 o 和小 o 符号的证明
Proof using big o and little o notation
我目前正在尝试证明，如果 g 在 o(f) 中，则 f 不在 O(g) 中。
我已经尝试定义任意变量来证明 g 是 o(f)，但我完全不知道下一步应该去哪里
如果 f ∊ O(g)，这意味着存在常数 c > 0 和 N，对于所有 n ≥ N，f(n) ≤ c * g(n)。
小o的definition就是如果g∊o(f)那么对于每一个常数ε>0，都有一些N'（不一定和上面的N一样）使得对于所有n ≥ N'，绝对值|g(n)| ≤ ε * f(n).
我们需要证明，如果第一个不等式成立，那么第二个不等式成立。首先将第一个不等式重新排列为 g(n) ≥ f(n)/c，然后选择 ε 为 0 和 1/c 之间的某个数。显然，对于 any n，以下两个不可能都成立，更不用说所有 n ≥ max(N, N')：
- g(n)≥f(n)/c
- |g(n)| ≤ ε * f(n) < f(n)/c
这是一个直接矛盾，所以f ∊ O(g) 和g ∊ o(f) 不能同时为真。
我目前正在尝试证明，如果 g 在 o(f) 中，则 f 不在 O(g) 中。
我已经尝试定义任意变量来证明 g 是 o(f)，但我完全不知道下一步应该去哪里
如果 f ∊ O(g)，这意味着存在常数 c > 0 和 N，对于所有 n ≥ N，f(n) ≤ c * g(n)。
小o的definition就是如果g∊o(f)那么对于每一个常数ε>0，都有一些N'（不一定和上面的N一样）使得对于所有n ≥ N'，绝对值|g(n)| ≤ ε * f(n).
我们需要证明，如果第一个不等式成立，那么第二个不等式成立。首先将第一个不等式重新排列为 g(n) ≥ f(n)/c，然后选择 ε 为 0 和 1/c 之间的某个数。显然，对于 any n，以下两个不可能都成立，更不用说所有 n ≥ max(N, N')：
- g(n)≥f(n)/c
- |g(n)| ≤ ε * f(n) < f(n)/c
这是一个直接矛盾，所以f ∊ O(g) 和g ∊ o(f) 不能同时为真。