这个问题在这里已有答案：
在具有Big O表示法和算法的渐近行为的特定情况下，我有点困惑。当我正在阅读描述这些符号的博客http://discrete.gr/complexity/时，我发现这个陈述是真是假：
A（n）算法是Θ（1）
答案说这取决于算法可能会或可能不会成立。在一般情况下，这是错误的。如果算法是Θ（1），那么肯定是O（n）。但如果它是O（n）那么它可能不是Θ（1）。例如，Θ（n）算法是O（n）但不是Θ（1）。
我正在努力理解这个答案。我知道Big O意味着程序可以渐近地变得更糟。所以我解释上面的陈述，其中O（n）比Θ（1）更差并且是真的。
有人能解释一个例子吗？
考虑optimized bubble sort，其具有渐近紧密的O（n2）上界，以及Ω（n）的渐近紧密下界（当数组已经被排序时）。项目的排列决定了算法必须执行的操作数量。
对比整数列表的整数。在这种情况下，您始终只需查看列表中的每个项目一次。上限为O（n），下限为Ω（n）。没有项目的安排会改变算法的复杂性。在这种情况下，当紧密的上限和下限相同时，我们说算法复杂度是Θ（n）。
如果算法是Θ（n），那么复杂性将永远不会超过O（n），并且它永远不会小于O（n）。所以它不可能是O（1）或Θ（1）。
但是如果算法被描述为O（n），则它可以是Ω（1）。例如，在整数列表中查找第一个非零值。如果列表中的第一项不为零，则您不必查看任何其他数字。但是，如果列表全部为零，则最终会查看所有列表。所以上限是O（n），下限是Ω（1）。
= Θ(1)），你肯定可以说你最多可以在一年内完成（= O(n)）。= O(n)），你不能确定你会在一周内完成（= Θ(1)）。= Θ(n)），你也可以说它最多需要一年（= O(n)），而且你确定它不能在一周内完成（≠ Θ(1)）。该示例基本上试图涵盖两个想法：
Θ(f(n))，则意味着它既是Ω(f(n))又是O(f(n))。它渐渐地既不比f(n)更好也不差，它具有相同的渐近行为。O(1)的函数可以看作是O(n)函数的子集。这可以概括，但不需要在这里过于正式，我想避免来自我身边的数学上不正确的灾难。这意味着如果它永远不会比常数更糟，那么它永远不会比线性函数更糟糕。因此，我们的想法是将Θ分解为O和Ω符号。然后确定哪个是哪个子集。
另外值得注意的是，任何算法（至少具有非零复杂度）都是Ω(1)。算法永远不会比常量做得更好。
示例哺乳动物是人类。
答案：不，不是一般的。然而，所有人都是哺乳动物。人类是哺乳动物的一个子集。
我试着想到另一个例子，但它太技术性或不够清晰。所以我会在这里留下这个不那么精美，但在这里清晰的图表。我通过谷歌搜索o omega theta并寻找图像。还有一些其他好的图像。
基本上，对于这个图中的每个函数f：它上面的任何东西都是Ω（f（n）），因为它永远不会比f做得更好，当n增加时它永远不会低于它;低于它的任何东西都是O（f（n）），因为它永远不会比f更糟，当n增加时它永远不会高于它。
该图并没有很好地显示常数的无意义渐近。还有其他图表更好地显示它。我只是把它放在这里，因为它一次有很多功能。