pro*_*er_ 1 c algorithm asymptotic-complexity data-structures
我知道大哦是上限,欧米茄是下限,但大多数地方我只看到大哦.
例如.在线性搜索算法中,最坏的情况是大哦(n).然而,搜索没有.可以在第一个地方找到.所以不行.输入是1.因此,这是最好的情况.所以,我们可以把它写成大欧米茄(1).但我已经看到,在许多地方,大哦也用于最佳情况,但我不知道为什么.
我知道两种符号之间的理论差异.但是,我实际上无法理解它.
有三个重要的复杂性类别:
重要的是要意识到O和Ω是松散的边界.它们不一定是最佳的.对于任何算法,存在无限数量的上界和无限数量的下界.
例如,可以说线性搜索具有O(n 2)的上限和Ω(1)的下限.我们知道它的实际复杂性介于这些界限之间.但是,通常情况下,说明非最佳边界并不常见.这些界限是正确的但没有用.
我们通常想要知道的是最小的上限和最大的下限.如果你说线性搜索是O(n 2),我可以改进你的答案并说不仅是O(n 2),它也是O(n).这是一个较小的上限,因此更有用.
不仅如此,你必须决定你是在考虑最坏的情况,平均情况还是最好的情况.除非另有说明,否则复杂性分析通常会考虑最坏的情况.因此,虽然您可能偶然发现了您正在寻找的项目,但线性搜索的最坏情况是必须查看所有n个项目.在最好的情况下的复杂性是O(1)但最坏的情况下是O(Ñ).
如果你能证明O =Ω-最小上界和最大下界是相同的 - 那么你现在知道Θ.在最坏的情况下,线性搜索由顶部的O(n)和底部的Ω(n)限制,因此其最坏情况复杂度恰好是Θ(n).
大多数人说算法是O(无论如何)应该使用Θ(无论如何).如果你知道边界是一个严格的上限和下限,那么Θ优于O.但是大多数人也不记得这些错综复杂,所以Big-O已成为Theta的懒惰后备.