Big Omega 是否意味着 little-oh
Does Big Omega imply little-oh
"If f= BigOmega(g) then g=o(f)"
这是真的吗？
我的理解是 f 是以 g 为界的 Big Omega。所以它至少在图上是 g(n) 或更多。因此，然后检查 g，如果它是 f 的 little-oh - 那么它应该至多但不包含 f 的边界。我觉得是真的？
不一定。令 f(x) = g(x) = x.
那么f = BigOmega(g)。证明：令 k = 1/2，n_0=1，则对于所有 n > n_0，f(n) >= k * g(n)（因为 x >= x/2当 x > 1).
然而，g != o(f)。如果让k=1/2，那么|g(n)| <= k * |f(n)|并非对所有 n.
"If f= BigOmega(g) then g=o(f)"
这是真的吗？ 我的理解是 f 是以 g 为界的 Big Omega。所以它至少在图上是 g(n) 或更多。因此，然后检查 g，如果它是 f 的 little-oh - 那么它应该至多但不包含 f 的边界。我觉得是真的？
不一定。令 f(x) = g(x) = x.
那么f = BigOmega(g)。证明：令 k = 1/2，n_0=1，则对于所有 n > n_0，f(n) >= k * g(n)（因为 x >= x/2当 x > 1).
然而，g != o(f)。如果让k=1/2，那么|g(n)| <= k * |f(n)|并非对所有 n.