算法的渐近行为和Big O比较
这个问题在这里已经有了答案：
考虑优化的气泡排序，其具有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和Ω符号。 然后确定哪些是其中的子集。
另外很高兴地注意到ANY算法（至少有一个非零复杂度）是Ω(1) 。 算法永远不会比常量做得更好。
哺乳动物的例子是人类。
答案 ：不，一般不会。 尽管所有人类都是哺乳动物。 人类是哺乳动物的一个子集。
我试图想到另一个例子，但它不是技术性太强，就是不够清楚。 所以我会在这里留下这张不太好画，但在这里清晰的图。 我通过搜索欧米茄theta并寻找图像发现。 还有其他一些好的图像。
基本上，对于这个图中的每个函数f：其上面的任何东西都是Ω（f（n）），因为它永远不会比f更好，当n增加时它永远不会低于它; 它下面的任何东西都是O（f（n）），因为它永远不会比f更坏，它随着n的增加永远不会超过它。
该图不能很好地显示常数的显着性。 还有其他图表显示它更好。 我只是把它放在这里，因为它一次有很多功能。
链接地址: http://www.djcxy.com/p/40045.html上一篇: Asymptotic behavior of algorithms and Big O comparison
下一篇: Whats the dominant term in 2^n or n^2 for big O notation