算法的渐近行为和Big O比较
Asymptotic behavior of algorithms and Big O comparison
在特定情况下，我对大 O 表示法和算法的渐近行为有些困惑。当我阅读很好地描述这些符号的博客 http://discrete.gr/complexity/ 时，我遇到了这个声明，无论它是对还是错：
一个 O( 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 和寻找图像找到了。还有一些其他的好图。
（来源：daveperrett.com）
基本上，对于此图中的每个函数 f：高于它的任何东西都是 Ω(f(n))，因为它永远不会比 f 做得更好，它永远不会随着 n 的增加而低于它；它下面的任何东西都是 O(f(n)) 因为它永远不会比 f 差，它永远不会随着 n 的增加而高于它。
该图没有很好地渐进地显示常数的微不足道。还有其他图表可以更好地显示它。我只是把它放在这里，因为它一次有很多功能。
在特定情况下，我对大 O 表示法和算法的渐近行为有些困惑。当我阅读很好地描述这些符号的博客 http://discrete.gr/complexity/ 时，我遇到了这个声明，无论它是对还是错：
一个 O( 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 和寻找图像找到了。还有一些其他的好图。
（来源：daveperrett.com）
基本上，对于此图中的每个函数 f：高于它的任何东西都是 Ω(f(n))，因为它永远不会比 f 做得更好，它永远不会随着 n 的增加而低于它；它下面的任何东西都是 O(f(n)) 因为它永远不会比 f 差，它永远不会随着 n 的增加而高于它。
该图没有很好地渐进地显示常数的微不足道。还有其他图表可以更好地显示它。我只是把它放在这里，因为它一次有很多功能。