大哦和欧米茄符号之间的区别究竟是什么？
我知道，大哦是上界，欧米茄是下界，但大多数地方我只看到很大的哦符号。
例如。 在线性搜索算法中，最坏的情况是大哦（n）。 但是，搜索没有。 可以在第一个地方找到。 所以不行。 的投入是1.因此，这是最好的情况。 所以，我们可以把它写成大欧米茄（1）。 但我已经看到，在很多地方，大哦也用于最好的情况，但我不知道为什么。
我知道两种符号之间的理论差异。 但是，我几乎无法理解它。
有三个重要的复杂类：
认识到O和Ω是松散的边界是很重要的。 它们不一定是最佳的。 任何算法都有无限数量的上界和下界数量无限。
例如，可以说线性搜索具有O（n2）的上界和Ω（1）的下界。 我们知道它的实际复杂性在于这些范围之间。 然而，通常情况下，状态非最优边界通常不会有帮助。 这些界限是正确的，但没有用处。
我们通常想要知道的是最小的上界和最大的下界。 如果你说线性搜索是O（n2），我可以改进你的答案，并说它不仅是O（n2），它也是O（n）。 这是一个较小的上限，因此更有用。
不仅如此，而且您必须决定是否查看最差情况 ， 平均情况或最佳情况 。 除非另有说明，否则复杂性分析通常会查看最坏的情况。 所以，虽然你可能偶然发现了你要找的物品，但是线性搜索的最坏情况是不得不查看所有n个物品。 最好的情况复杂度是O（1），但最坏的情况是O（n）。
如果你能证明O =Ω--即最小上界和最大下界相同，那么你现在知道Θ。 线性搜索在最坏的情况下，由顶部的O（n）和底部的Ω（n）限定，因此其最坏情况下的复杂度恰好为Θ（n）。
大多数说算法的人是O（无论）应该使用Θ（无论）。 如果你知道界限是一个严格的上界和下界，那么Θ比O好。但是大多数人也不记得这些错综复杂的东西，所以Big-O已经成为了Theta的懒惰后备。
我知道两种符号之间的理论差异。 但是，我几乎无法理解它。
大O在描述算法时被广泛使用，因为知道算法运行得有多糟，所以工程师可以为任何情况做好准备。
然而，大欧米茄通常并不像大O那样有用。虽然知道算法运行的速度有多快，但当设计软件工程师需要知道最坏情况的情况时，再次为任何情况做好准备。
当人们说运行时间是O（f（n））时，它们意味着运行时间属于O（f（n））的函数类。
即，对于一些c和每个n> = 0，f（n）<= cn
在你的线性搜索的具体问题中，最糟糕的情况确实需要一些时间，即O（N）。
最好的情况将需要不变的时间 - T = k 。 但是k属于类O（1）（因为对于某些+ ve Epsil，k <ε+ k）。 所以我可以说，在最好的情况下，运行时间是O（1）。
也就是说，人们用O（f（N））松散地表示它与f（N）“有些成正比”。
链接地址: http://www.djcxy.com/p/40179.html上一篇: What exactly is the difference between big oh and omega notation?