Dan*_*lan 2 algorithm big-o computer-science big-theta
我的理解是,如果一个算法是O(1)它也是O(n),O(n^2),O(n^3)等这使得它显得有些苍白无力.例如,如果有人问我任何算法的Big-Oh表示法,我可以在O(n^n)不考虑它的情况下(字面意思)说,并且在大多数情况下在技术上是正确的.
既然(这是我的理解)这是真的,这有用的信息怎么样？使用类比,如果我问某人他们拥有多少房子,那么"1到无限"这样的答案就不是很有用.一个有用的答案(这有点像Big-Theta)将是"1".
Big-O建立一个上限.如果您知道算法是O(n 2),那么您就知道它的复杂性是最差的二次方.它实际上可能是O(n)或O(1)但它绝对不是O(n 3).找出算法的运行时上限是非常有用的.
问题是"这个算法的大O是什么？"这是正确的.措辞不好."the"这个词不正确.算法中没有一个Big-O.有许多.无限多.Big-O没有建立一个紧张的上限.这就是Big-Theta的用武之地.Big-Theta断言了上限和下限:它给出了一个精确的渐近界.问题应该是,"这个算法的Big-Theta是什么？"
但重要的是不要抛出Big-O,因为并非所有算法都具有已知的精确边界.矩阵乘法是众所周知的问题,没有已建立的Big-Theta.朴素算法是O(n 3),现有技术是O(n 2.3727).这是一个上限,但它可能不是的(最佳)的上限.Big-Theta位于O(n 2.3727)和Ω(n 2)之间.