algorithm - 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)) 不正确，第一个关系不正确。