Ari*_*iel 6 language-agnostic algorithm complexity-theory big-o time-complexity
如果我们有一个大小随机的整数数组n，我们需要计算总和。
声明：最好的算法在O(n)
但是，我声称我们可以在O(1). 为什么？
我们肯定知道它n被锁定在某个字段中（因为它是 int 并且 int 是有限的）这意味着我可以在不到 2,147,483,647 个步骤中对所有元素求和？
eer*_*ika 15
为什么不是每个算法都是 O(1)？
因为我们在分析算法的复杂性时选择忽略具体计算机的局限性（即假设资源是无限的）。
渐近复杂性为我们提供了有关复杂性如何增长的有用信息。仅仅得出结论认为由于硬件而存在恒定限制并且忽略如何达到限制并不能为我们提供有价值的信息。
此外，你所感知的极限在现实中要高得多。计算机不限于表示最多 2'147'483'647 个整数值。使用复杂的数据结构，计算机可以表示任意大的数字 - 直到内存用完......但内存可以从磁盘流式传输。还有一些数据中心可以轻松提供数百兆兆字节的存储。
虽然，公平地说：如果我们允许任意长度的整数，那么总和的复杂度比线性差，因为即使是单个加法也具有线性复杂度。
一旦我们采取具体硬件考虑，更有意义的选择在分析中使用的混凝土单位：有多少秒做的程序采取一些具体的投入在这个特定的硬件？而找到答案的方法不是数学，而是具体的测量。
为什么不是每个算法都是 O(1)？
TL;DR：因为Big O符号用于量化算法，关于它如何随着输入的增加而表现。
非正式地，您可以将其视为人类发明的用于量化算法类别的框架。如果这样的框架对每个算法都产生影响O(1)，那么它首先就违背了它自己的目的，即 量化算法的类别。
更详细的回答
让我们首先澄清Big O当前上下文中什么是符号。从（来源）可以阅读：
Big O 表示法是一种数学表示法，它描述了当参数趋向于特定值或无穷大时函数的限制行为。(..)在计算机科学中，大 O 符号用于根据算法的运行时间或空间要求随着输入大小的增长而增长的情况进行分类。
以下说法不准确：
但是，我声称我们可以在 O(1) 中做到这一点。为什么？我们肯定知道 n 被锁定在某个字段中（因为它是 int 并且 int 是有限的）这意味着我可以在不到 2,147,483,647 个步骤中对所有元素求和？
不能简单地执行“O(2,147,483,647)”并声称“O(1)”，因为该Big O符号不代表一个函数，而是一组具有某个渐近上限的函数；正如人们可以从源代码中读取的那样：
Big O 表示法根据函数的增长率来表征函数：具有相同增长率的不同函数可以使用相同的
O表示法来表示。
非正式地，在计算机科学的时间复杂度和空间复杂度理论中，人们可以将Big O符号视为算法的分类，分别具有关于时间和空间的某种最坏情况。例如O(n)：
如果算法的时间/空间复杂度为 O(n)，则称该算法采用线性时间/空间或 O(n) 时间/空间。非正式地，这意味着运行时间/空间最多随输入（source）的大小线性增加。
所以复杂性是O(n)因为随着输入的增加，复杂性线性增长而不是恒定的。
承认所有算法的复杂度为 O(1) 的理论几乎没有用。
在复杂性理论中，N 是一个无界变量，因此您确实可以获得一个非平凡的渐近界。
对于实际算法，渐近复杂度是有用的，因为它确实为 N 的中等值（远低于最大int）的精确复杂度建模。
在某些病理情况下（例如最复杂的矩阵乘法算法），int在渐近行为变得有益之前，N 必须超过 a 的容量。
旁注：
我记得一篇论文声称某个操作的时间为 O(1)。该操作涉及像素值的直方图，其范围确实是恒定的。但这是一个误导性的技巧，因为隐藏常数对于 8 位图像与 256 成正比，对于 16 位图像与 65536 成正比，这使得算法非常缓慢。声称 O(H) 其中 H 是 bin 的数量会提供更多信息和更诚实。