任何人都可以解释大O与大欧米茄vs Big Theta？
可能重复：
Big Theta Notation - 大Theta代表什么？
我想我理论上理解这一点，但我难以理解的是三者的应用。
在学校，我们总是用Big O来表示算法的复杂性。 例如，泡泡排序为O（n ^ 2）。
现在阅读更多的理论后，我得到了大哦不是唯一的措施，至少有两个有趣的。
但这是我的问题：
大O是上限，大欧米茄是下限，Big Theta是两者的组合。 但是这在概念上意味着什么？ 我明白图表上的含义; 我见过一百万个这样的例子。 但是算法的复杂性意味着什么？ “上限”或“下限”如何与此混合？
我想我只是没有得到它的应用。 我知道如果乘以某个常数c，如果在某个值n_0 f（x）大于g（x）后，f（x）被认为是O（g（x））。 但是这实际上意味着什么？ 为什么我们将f（x）乘以某个值c？ 地狱，我认为与大O符号倍数无关紧要。
大O符号和它的亲戚，大的Theta，大的Omega，小的o和小的omega是说明某个函数如何在极限点上行为的方式（例如，当接近无限时，但当接近时0等），而没有多说这个函数。 它们通常用于描述算法的运行空间和时间，但也可以在其他数学领域中看到渐近行为。
半直观的定义如下：
如果“从某点开始”，g（x）低于c * f（x），那么函数g（x）被认为是O（f（x）），其中c是某个常数。
其他定义是相似的，Theta要求g（x）在f（x）的两个常数倍数之间，欧米茄要求g（x）> c * f（x），小版本要求这对所有的常量。
但为什么有趣的说，例如，一个算法的运行时间为O（n ^ 2）？
这很有趣，主要是因为在理论计算机科学中，我们最关心算法如何处理大量输入。 这是事实，因为对于小输入，算法运行时间可能因实现，编译，硬件以及其他在理论上分析算法时没有意思的事情而大不相同。
但是，增长率通常取决于算法的性质，为了改进它，您需要对您正试图解决的问题有更深入的了解。 例如，排序算法就是这种情况，您可以在O（n ^ 2）中获得一个简单的算法（Bubble Sort），但为了将其提高到O（n log n），您需要一个真正的新思路如合并排序或堆排序中引入的那样。
另一方面，如果你有一个运行在5n秒内的算法，而另一个运行在1000n秒内（例如n = 3的长时间打哈欠和发射中断之间的差异），当你得到n = 1000000000000，规模的差异似乎不那么重要。 如果你的算法需要O（log n），你必须等待log（1000000000000）= 12秒，或许乘以某个常量，而不是几乎317，098年，而不管常量有多大是，是一个完全不同的规模。
我希望这使事情更清楚一点。 祝你好运！
链接地址: http://www.djcxy.com/p/39653.html上一篇: Could anyone explain Big O versus Big Omega vs Big Theta?
下一篇: What the operator `<