Big-O表示法1 / O（n）= Omega（n）

符号1 / O（n）=Ω（n）有点模糊。实际上，它本身没有O（n），只有f（n）〜O（n），这是关于函数f的值的声明（存在常数C，因此f（n）<每n个Cn）。 如果我正确理解的话，证明语句是“如果函数f（n）是O（n）而不是1 / f（n）是Ω（n）\”，则形式为： f（n）〜O（n）=> 1 / f（n）〜Ω（n） 编辑：除非我不认为我理解正确，因为f（n）= 1〜O（n），但是1 / f（n）= f（n）= 1显然不是Ω（n ）。分配f（n）〜O（n）=> 1 / f（n）〜Ω（1 / n）不是吗？ 编辑：不同的人倾向于使用不同的运算符。最常见的是f（n）= O（n），但这是令人困惑的，因为右侧不是函数，因此它不能是正等式。我们通常在学校中使用f（n）〜O（n），虽然混淆性较小，但仍与该运算符在一般对等关系中的常用用法不一致。最一致的算子为f（n）∈O（n），因为可以将右手侧合理地视为函数集。     

对于某些多项式函数f（x），某些多项式函数g（x）和O（f（x）），O（n）或多或少意味着以下内容： 在大小方面，我们有| f（x）| <= M | g（x）|，对于一些M。基本上，f的上限是固定时间g。 Ω（n）表示，对于某些多项式h（x），某些多项式k（x）和Ω（h（x））： 在大小上，| h（x）| > = M | k（x）|，对于一些M。基本上，h的下限为常数k。 因此，对于（O（f（x）））^-1，1 / | f（x）| <= 1 /（M | g（x）|）。 稍微重新排列即可得出M | g（x）| <= | f（x）| -即f（x）的下限是常数乘以g，这与我们对上面Ω（n）的定义完全相同。 正式证明有点不容易，但是应该可以帮助您入门。