f(n) 的上限的下限是否等于 f(n) 的下限的上限

Question

断言：

Ω(O(f(n))) = O(Ω(f(n)))

为了反驳，我只需要给函数f(n)一个反例，

所以令 f(n) = n 假设

K1 <= n <= K4 ; where K1, K4, n > 0

因此：

O(n) = K4 ; where K3 <= K4 <= K5 for some K3, K5 > 0

Ω(n) = K1 ; where K0 <= K1 <= K2 for some K1, K2 > 0

现在，

O(K1) = K2

Ω(K4) = K3

我现在可以声明，K2 <= K3 因此断言不被批准吗？？但是，如果平等呢？？

Answer 1

您的论点不正确，因为以下部分；

K1 <= n <= K4 ; where K1, K4, n > 0

你不能用数字K1和K4来证明或否定这些关系，因为在asymptotic notations中你应该使用function.

您可以使用以下解决方案来拒绝此关系：

f(n) = n

h(n) = O(f(n)) => h(n) <= f(n)

我假设（反例）

h(n) = n

对于关系的右边，我假设

f(n) = n

g(n) = Ω(f(n)) => f(n) <= g(n)

我假设（反例）

g(n) = log n

通过替换我们拥有的第一个关系中的这些函数；

Ω(O(f(n))) = O(Ω(f(n))) =>

Ω(h(n)) = O(g(n)) =>

Ω(n) = O(log n)

同理，我们可以假设：

k(n) = Ω(n)

我假设（反例）

k(n) = n

最后我们有：

Ω(n) = O(log n) =>

n = O(log n)

这个结果（n = O(log n)）不正确，第一个关系也不正确。

Can Lower bound of Upper bound of f(n) equal Upper bound of Lower bound of f(n)