我的理解是，如果一个算法是O(1)，它也是O(n)，，等等，这使它看起来毫无用处O(n^2)。O(n^3)例如，如果有人问我任何算法的 Big-Oh 符号，我可以直接说O(n^n)而不考虑它（字面意思）并且大部分时间在技术上是正确的。
既然（我的理解是）这是真的，那么这些有用的信息如何？打个比方，如果我问某人他们拥有多少房子，“1 到无穷大”这样的答案并不能提供很多信息。一个有用的答案（这有点像 Big-Theta）是“1”。
问问题
934 次
3 回答
7
Big-O 建立了一个上限。如果你知道一个算法是 O(n 2 )，那么你就知道它的复杂度是最坏的二次方。它实际上可能是 O(n) 或 O(1)，但绝对不是 O(n 3 )。找出算法运行时的上限非常有用。
你是对的，“这个算法的 Big-O 是什么？”这个问题是正确的。措辞不好。“那个”这个词是不正确的。没有一个算法的大 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 ) 之间。
于 2013-09-24T21:51:51.893 回答
1
这是Donald Knuth向美国数学会提出 O 表示法的一封信
于 2013-09-25T01:07:47.440 回答
0
说任何算法都是 O(n^n) 是不正确的，因为 big-Oh 指的是严格的上限。我们也不是说算法是 O(n^n)，而是算法的时间复杂度是 O(n^n)。
我希望这可以澄清事情。
于 2013-12-10T22:09:39.703 回答