大O用于有限的,固定大小的可能值集合

Question

这个问题引发了一些混乱,并且很多评论关于在各种答案中提出的算法是O(1)还是O(n).

让我们用一个简单的例子来说明两个观点:

我们希望找到一个长期x这样a * x + b = 0,在a与b已知的,非空多头.

• 一个明显的O(1)算法是 x = - b / a
• 一个慢得多的算法将包括测试每个可能的长值,平均约为2 ^ 63倍.

第二个算法是O(1)还是O(n)？

相关问题中提出的论点是:

• 它是O(n),因为在最坏的情况下,你需要遍历所有可能的长值
• 它是O(1)因为它的复杂性是形式c x O(1),其中c = 2^64是一个常数.

虽然我理解说它是O(1)的论点,但感觉反直觉.

ps:我添加了java,原始问题是Java,但这个问题与语言无关.

Answer 1

只有存在变量N时,复杂性才有意义.因此,问题没有任何意义.如果问题是:

一个慢得多的算法将包括在N个值范围内测试每个可能的值,平均值将慢大约N倍.

第二个算法是O(1)还是O(N)？

然后答案是:这个算法是O(N).

Answer 2

Big O描述了算法的性能如何随着输入大小n的缩放而缩放.换句话说,当您在更多输入数据上运行算法时.

在这种情况下,输入数据是固定大小,因此两种算法都是O(1),尽管具有不同的常数因子.

如果你用"n"表示数字中的位数(即你删除了64位长的限制),那么你可以分析给定的位大小n算法如何缩放.

在这种情况下,第一个仍然是O(1) (参见Qnan的评论),但第二个现在是O(2 ^ n).

我强烈建议您观看麻省理工学院"算法导论"课程的早期讲座.它们是Big O(和Big Omega/Theta)的一个很好的解释,尽管我们很好地掌握了数学.