这个问题引发了一些困惑和许多关于各种答案中提出的算法是 O(1) 还是 O(n) 的评论。
我们用一个简单的例子来说明这两种观点：
我们想找到一个 long
x，使得a * x + b = 0，在哪里a和b是已知的，非空 long。
x = - b / a第二种算法是 O(1) 还是 O(n)？
链接问题中提出的论点是：
c x O(1)，其中c = 2^64是一个常数。虽然我理解说它是 O(1) 的论点，但感觉违反直觉。
ps：我添加了java，因为原始问题是Java，但这个问题与语言无关。
仅当存在变量 N 时，复杂性才相关。因此，这个问题没有任何意义。如果问题是：
一个更慢的算法将包括在 N 个值的范围内测试每个可能的值，这平均会慢 N 倍。
第二种算法是 O(1) 还是 O(N)？
那么答案是：这个算法是 O(N)。
Big O 描述了算法的性能将如何随着输入大小 n 的缩放而缩放。换句话说，当您在更多输入数据上运行算法时。
在这种情况下，输入数据是固定大小的，因此两种算法都是 O(1)，尽管具有不同的常数因子。
如果您将“n”表示数字中的位数（即您删除了它是 64 位长的限制），那么您可以分析给定的位大小 n 算法如何扩展。
在这种情况下，第一个仍然是 O(1) （参见 Qnan 的评论），但第二个现在是 O(2^n)。
我强烈推荐观看麻省理工学院“算法导论”课程的早期讲座。它们是对大 O（和大欧米茄/西塔）的一个很好的解释，尽管确实假设对数学有很好的掌握。
检查解决方案中每个可能的输入是 O(2^N) 的位数。当您使位数恒定时，两种算法都是 O(1)，您知道需要检查多少个解决方案。
事实：你在计算机上实际运行的每个算法都是 O(1)，因为宇宙的计算能力是有限的（有有限的原子，自大爆炸以来已经过去了有限的秒数）。
这是真的，但不是一种非常有用的思考方式。当我们在实践中使用 big-O 时，我们通常假设所涉及的常数相对于渐近项是很小的，因为否则仅给出渐近项并不能告诉您算法如何执行的太多信息。这在实践中效果很好，因为常量通常是“我使用数组还是哈希映射”之类的东西，最多相差 30 倍，输入是 10 ^ 6 或 10 ^ 9，所以二次方之间的差异线性算法比常数因素更重要。不遵守此约定的大 O 讨论（如算法＃2）是毫无意义的。
无论 a 或 b 的值是什么，最坏的情况仍然是检查 2^64 或 2^32 或 2^somevalue 值。该算法的复杂度在 O(2^k) 时间内，其中 k 是用于表示长值的位数，如果我们考虑 a 和 b 的值，则为 O(1) 时间。