algorithm - 为什么不是每个算法都是 O(1)？

Question

如果我们有一个大小为 n 的随机整数数组这样我们就需要计算总和。
claim :最好的算法在 O(n) 中做到了这一点
但是，我声称我们可以在 O(1) 中做到这一点.为什么？
我们肯定知道n被锁定在某个字段中(因为它是 int 并且 int 是有限的)这意味着我可以在不到 2,147,483,647 个步骤中对所有元素求和？

Answer 1

Why isn't every algorithm O(1)?

因为在分析算法的复杂性时，我们选择忽略具体计算机的局限性(即假设资源是无限的)。
渐近复杂性为我们提供了有关复杂性如何增长的有用信息。仅仅得出结论认为由于硬件而存在恒定限制并且忽略如何达到限制并不能为我们提供有值(value)的信息。

此外，你所感知的极限在现实中要高得多。计算机不限于表示最多 2'147'483'647 个整数值。使用复杂的数据结构，计算机可以表示任意大的数字 - 直到内存用完......但内存可以从磁盘流式传输。还有一些数据中心可以轻松提供数百兆兆字节的存储。
虽然，公平地说:如果我们允许任意长度的整数，那么总和的复杂度比线性差，因为即使是单个加法也具有线性复杂度。

一旦我们考虑到具体的硬件，在分析中选择使用具体的单位就更有意义了:对于这个特定硬件上的一些具体输入，程序需要多少秒？而找到答案的方法不是数学，而是具体的测量。