怎么了O（1）？
在讨论涉及散列和searchtypes的algorithm时，我一直注意到O（1）的一些非常奇怪的用法，通常是在使用由语言系统提供的字典types的情况下，或者使用使用数组的字典或散列数组types指数表示法
基本上，O（1）是指以一个固定的时间和（通常）固定的空间为界。 一些相当基本的操作是O（1），虽然使用中间语言和特殊的虚拟机往往扭曲在这里思考的人（例如，如何摊销垃圾收集器和其他dynamic的过程，否则会O（1）活动）。
但是忽略了延迟的分期，垃圾收集等等，我还是不明白，除非是在非常特殊的条件下，假设某些涉及某种search的技术可以是O（1）。
虽然我之前已经注意到了这个问题，但是在Pandincus问题中出现了一个例子，“在C＃.NET中使用O（1）时间获取项目的'正确'集合？ 。
正如我在那里提到的那样，我所知道的唯一的集合提供了O（1）访问作为保证边界，它是一个固定边界数组，具有整数索引值。 假定数组是通过映射到使用O（1）操作来定位具有该索引的单元的随机存取存储器来实现的。
对于涉及某种search以确定不同types索引（或具有整数索引的稀疏数组）的匹配单元的位置的集合，生活并不那么容易。 特别是，如果有碰撞和拥塞是可能的，访问不完全是O（1）。 如果集合是灵活的，则必须认识并分摊扩展拥塞缓解（例如，高的碰撞发生率或树不平衡）的基础结构（例如树或散列表）的成本。
我永远不会想到把这些灵活和dynamic的结构说成是O（1）。 然而，我认为他们提出的O（1）解决scheme没有任何必须保持的条件，以确保（1）访问得到保证（以及有恒定的可以忽略的小）。
问题：所有这些准备工作都是一个问题。 O（1）的休闲是什么？为什么盲目接受？ 即使接近于常数，即使O（1）可能会不理想地大，是否认识到呢？ 或者是（1）简单地将计算复杂性概念挪用于非正式使用？ 我感到困惑。
更新：答案和评论指出了我自己定义O（1）的地方，而且我已经修复了这个问题。 我仍然在寻找好的答案，有些评论线索比他们的答案更有趣，在一些情况下。
我的理解是，O（1）不一定是恒定的; 相反，它不依赖于所考虑的variables。 因此，对于散列中的元素的数量，散列查找可以被认为是O（1），而不是相对于被散列的数据的长度或者散列中的元素与存储桶的比率。
混淆的另一个因素是大O符号描述限制行为。 因此，对于N的小值，函数f（N）确实可以显示出很大的变化，但是如果说N是接近无限的极限相对于N是恒定的，那么你仍然是正确的。
问题在于人们对于术语来说确实很</s> </s>。 这里有三个重要但不同的课程：
O（1）最坏的情况
这很简单 – 在最坏的情况下，所有的操作都会花费不变的时间，因此在任何情况下都是如此。 访问一个数组的元素是O(1)最差的情况。
O（1）摊销最坏的情况
摊销意味着在最坏的情况下并不是每个操作都是O(1) ，但是对于任何N个操作序列，在最坏的情况下序列的总成本不是O(N) 。 这意味着，即使我们不能用一个常量限制任何单个操作的成本，总是会有足够的“快速”操作来弥补“慢”操作，使得操作序列的运行时间是线性的在操作的次数。
例如，标准的dynamic数组（Dynamic Array）在填满时将其容量加倍，即使有些插入需要O(N)时间，也需要O(1)分摊时间来插入元素 – 总是有足够的O(1)插入插入N个项目总是需要O(N)时间。
O（1）平均情况
这一个是最棘手的。 平均情况有两种可能的定义：一种是固定input的随机algorithm，另一种是随机input的确定性algorithm。
对于具有固定input的随机algorithm，我们可以通过分析algorithm并确定所有可能的运行时间的概率分布，并计算该分布的平均值（取决于algorithm，这可能是可能由于停机问题而不可能）。
在另一种情况下，我们需要一个input的概率分布。 例如，如果我们要测量sortingalgorithm，那么一个这样的概率分布将是具有全部N的分布。 投入的可能排列同样可能。 然后，平均运行时间是所有可能input的平均运行时间，由每个input的概率加权。
由于这个问题的主题是哈希表，这是确定性的，我将重点讨论平均情况的第二个定义。 现在，我们不能总是确定input的概率分布，因为我们可以对任何东西进行散列，这些项可能来自用户在文件系统中input或从文件系统中input。 因此，在讨论哈希表时，大多数人只是假设input行为良好，并且哈希函数performance良好，使得任何input的哈希值基本上随机分布在可能的哈希值的范围内。
花一点时间，让最后一点沉入 – 哈希表的O(1)平均情况性能来自于假设所有哈希值是均匀分布的。 如果这个假设被违背（通常不是这样，但肯定会发生），运行时间平均不再是O(1) 。
另请参阅按algorithm复杂性拒绝服务 。 在本文中，作者讨论了他们如何利用两个版本的Perl使用的默认哈希函数的一些弱点来生成大量的带有哈希碰撞的string。 通过这个string列表，他们通过向Web服务器提供这些string，从而在Web服务器使用的哈希表中产生最坏情况的O(N)行为，从而对某些Web服务器产生了拒绝服务攻击。
O（1）表示恒定的时间和（通常）固定的空间
只是澄清这些是两个单独的陈述。 你可以有O（1）在时间，但O（N）在空间或任何。
即使近乎恒定，即使O（1）可能会不合需要地被认识到吗？
O（1）可能是不切实际的巨大的，它仍然是O（1）。 常常被忽视的是，如果你知道你将拥有一个非常小的数据集，常数比复杂性更重要，对于相当小的数据集来说，它是两者的平衡。 如果数据集的常量和大小是合适的，则O（n！）algorithm可以执行O（1）。
O（）表示法是复杂性的一个度量 – 不是algorithm将要花费的时间，也不是一个给定algorithm的“好”的纯粹度量。
我可以看到你在说什么，但是我认为有一些基本的假设，在Hash表中查找的复杂度是O（1）。
- 哈希函数是合理devise的，以避免大量的冲突。
- 这组密钥是非常随机分布的，或者至less不是故意devise的，以使哈希函数性能不佳。
哈希表查找的最坏情况复杂度是O（n），但是考虑到上面的两个假设，这是非常不可能的。
散列表是一种支持O（1）search和插入的数据结构。
散列表通常具有一个键和值对，其中键被用作函数的参数（ 散列函数 ），该函数将确定值在其内部数据结构 （通常是数组）中的位置。
由于插入和search仅取决于散列函数的结果，而不取决于散列表的大小和存储的元素的数量，散列表具有O（1）插入和search。
有一个警告 ，但是。 也就是说，随着散列表变得越来越饱满，散列函数将返回已经被占用的数组的元素的散列冲突 。 这将需要一个碰撞解决scheme ，以find另一个空的元素。
发生散列冲突时，在O（1）时间内无法执行search或插入操作。 然而， 良好的碰撞解决algorithm可以减less尝试查找另一个可空闲空间的次数，或者增加散列表大小可以首先减less碰撞次数。
所以，从理论上讲， 只有一个由数组元素和完美哈希函数组成的数组支持的散列表才能够实现O（1）性能 ，因为这是避免散列冲突的唯一方法，所需的操作。 因此，对于任何有限大小的arrays，由于散列冲突，将会小于O（1）。
我们来看一个例子。 让我们使用散列表来存储以下(key, value)对：
-
(Name, Bob) -
(Occupation, Student) -
(Location, Earth)
我们将使用100个元素的数组来实现散列表后端。
该key将用于确定存储（ key ， value ）对的数组元素。 为了确定元素，将使用hash_function ：
-
hash_function("Name")返回18 -
hash_function("Occupation")返回32 -
hash_function("Location")返回74 。
从上面的结果中，我们将(key, value)对分配给数组的元素。
array[18] = ("Name", "Bob") array[32] = ("Occupation", "Student") array[74] = ("Location", "Earth")
插入只需要使用散列函数，并不依赖于散列表的大小和它的元素，所以它可以在O（1）时间执行。
同样，search一个元素使用散列函数。
如果我们要查找关键字"Name" ，我们将执行一个hash_function("Name")来找出数组中的哪个元素所需的值。
此外，search不依赖于哈希表的大小，也不取决于存储的元素的数量，因此是O（1）操作。
一切都很好。 让我们尝试添加一个额外的条目("Pet", "Dog") 。 然而，有一个问题，因为hash_function("Pet")返回18 ，这是"Name"键相同的散列。
因此，我们需要解决这个散列冲突。 假设我们使用的散列冲突解决函数发现新的空元素是29 ：
array[29] = ("Pet", "Dog")
由于在这个插入中有一个哈希碰撞，我们的性能不是完全O（1）。
当我们尝试search"Pet"键时，这个问题也会出现，因为试图通过执行hash_function("Pet")来查找包含"Pet"键的元素将始终返回18。
一旦我们查找元素18，我们将find关键"Name"而不是"Pet" 。 当我们发现这个不一致的时候，我们需要解决冲突，以便检索包含实际"Pet"键的正确元素。 解决哈希碰撞是一个额外的操作，使哈希表不能在O（1）时间执行。
我不能和其他你所见过的讨论交谈过，但是至less有一个散列algorithm可以保证是O（1）。
杜鹃散列保持一个不variables，因此散列表中没有链接。 插入是摊销O（1），检索总是O（1）。 我从来没有见过它的实现，这是我在大学时最近发现的东西。 对于相对静态的数据集，它应该是一个很好的O（1），因为它计算两个散列函数，执行两次查找，并立即知道答案。
请注意，这是假设哈希计算也是O（1）。 你可以争辩说，对于长度为K的string，任何散列都是最小的O（K）。 实际上，你可以很容易地把K简化成K，如果K <1000，那么K（K）= O（1）。
对于如何理解Big-Oh符号，可能存在一个概念错误。 这意味着，给定一个algorithm和一个input数据集，当数据集的大小趋向于无穷大时，algorithm运行时间的上限取决于O函数的值。
当说一个algorithm花费O（n）时间时，这意味着algorithm的最坏情况的运行时间线性地依赖于input集合的大小。
当一个algorithm花费O（1）次时，它唯一意味着的是给定一个计算函数f（n）的运行时间的函数T（f），存在一个自然的正数k，使得T（f） <k为任何inputn。 实际上，这意味着algorithm的运行时间的上限不取决于其大小，并且具有固定的有限的限制。
现在，这并不意味着这个限制很小，只是它与input集的大小无关。 所以如果我为数据集的大小人为地定义一个边界k，那么它的复杂度就是O（k）== O（1）。
例如，search链表上的值的实例是O（n）操作。 但是如果我说列表最多有8个元素，那么O（n）变成O（8）变成O（1）。
在这种情况下，我们使用了一个trie数据结构作为字典（一个字符树，其中叶节点包含用作键的string的值），如果键是有界的，则其查找时间可以被认为是O（ 1）（如果我将字符字段定义为长度至多为k个字符，对于许多情况这可能是合理的假设）。
对于一个散列表，只要你假设散列函数是好的（随机分布的）并且足够稀疏以便使冲突最小化，并且在数据结构足够密集时执行重新散列，那么你的确可以认为它是一个O（1 ）访问时间结构。
总之，O（1）时间可能被高估了很多东西。 对于大型数据结构来说，适当的散列函数的复杂性可能不是微不足道的，并且存在充足的angular落情况，其中碰撞的数量导致其performance得像O（n）数据结构，并且重新散列可能变得非常昂贵。 在这种情况下，像AVL或B-tree这样的O（log（n））结构可能是更好的select。
总的来说，我认为人们比较使用它们，而不考虑正确性。 例如，基于散列的数据结构是O（1）（平均）查找，如果devise得好，你有一个很好的散列。 如果一切都散列到一个桶，那么它是O（n）。 一般来说，虽然使用了一个好的algorithm，而且密钥分布合理，所以如果不具备所有的资格，就可以很方便地将其描述为O（1）。 同样的列表，树木等。我们考虑到某些实现，谈论它们时，谈论它们时简单得多，没有资格。 另一方面，如果我们正在讨论具体的实现，那么可能会更精确。
HashTable的查找方式与表中的项目数相比是O（1），因为不pipe添加到列表中的项目数多less，散列单个项目的成本几乎相同，创build哈希将告诉你的项目的地址。
为何回答这个问题：OP问及为何O（1）在他心目中似乎如此随便乱丢，显然在很多情况下并不适用。 这个答案解释说，在这种情况下，O（1）时间确实是可能的。
O（1）的意思是，algorithm的时间复杂度是固定的值。 这并不意味着它是不变的，只是它是有界的，不pipeinput值。 严格地说，许多据称O（1）时间algorithm实际上并不是O（1），只是走得太慢，以至于它们都被限制在所有的实际input值上。
是的，垃圾收集确实会影响运行在垃圾收集舞台上的algorithm的渐近复杂性。 这不是没有成本的，但是如果没有经验的方法来分析是非常困难的，因为交互成本不是成分的。
垃圾收集的时间取决于所使用的algorithm。 典型的现代垃圾收集器切换模式为内存填充，以控制这些成本。 例如，当内存压力低时，常用的方法是使用Cheney风格的复制收集器，因为它支付与现场设置的大小成比例的成本以换取使用更多空间，并且当内存压力切换到标记和扫描收集器变得更大，因为即使它支付成本与标记的现场设置和整个堆或清扫的死亡成比例。 当你添加卡片标记和其他优化等时，实际的垃圾收集器的最坏情况成本实际上可能会差一点，为一些使用模式提供额外的对数因子。
所以，如果你分配一个大的哈希表，即使你使用O（1）的search来访问它，但是如果你在一个垃圾回收的环境中这样做，偶尔垃圾回收器会遍历整个数组，因为它大小为O（n），您将在收集期间定期支付这笔费用。
我们通常从algorithm的复杂性分析中排除它的原因是垃圾收集以非平凡的方式与您的algorithm交互。 它的成本有多差很大程度上取决于你在同一过程中做了什么，所以分析不是组成的。
此外，除了复制与紧凑与标记和扫描问题之外，实现细节可能会极大地影响最终的复杂性：
- 跟踪脏位的增量垃圾收集器等都可以使那些较大的重新遍历消失。
- 这取决于GC是按照挂钟时间定期工作，还是按照分配数量运行。
- 标记和扫描风格algorithm是并行还是停止世界
- 它是否标记新的分配黑色，如果它留下白色，直到它把它们放入一个黑色的容器。
- 不pipe你的语言是否允许修改指针，都可以让一些垃圾收集器一次性工作。
最后，在讨论一个algorithm的时候，我们正在讨论一个稻草人。 渐近线将永远不会完全包含您的环境的所有variables。 你很less执行所devise的数据结构的每个细节。 你在这里和那里借用一个特性，因为你需要快速无序的密钥访问，所以你使用了一个散列表，你可以使用一个union-find来寻找包含path压缩的不相交集合，通过rank来合并内存区域，因为你不能当你合并他们或你有什么时，他们可以支付与地区大小成正比的成本。 这些结构被认为是原始的，当规划整个结构的整体性能特征时，渐近线可以帮助你，但知道常量是多么的重要。
你可以用完美的O（1）渐近特征来实现这个哈希表，只是不要使用垃圾收集。 将其从文件映射到内存中并自行pipe理。 你可能不会喜欢涉及到的常量。
哈希表实现实际上不是“正好”O（1）在使用，如果你testing一个，你会发现他们平均大约1.5查找来find一个给定的键跨越一个大的数据集
（由于碰撞DO发生的事实，碰撞时必须分配不同的位置）
另外，在实践中，HashMaps是由具有初始大小的数组支持的，当它平均达到70％的饱满度时，“增长”到两倍大小，这提供了相对较好的寻址空间。 70％的饱满碰撞率增长更快。
大O理论指出，如果你有O（1）algorithm，甚至O（2）algorithm，关键因素是input集大小和插入/取出其中一个的步骤之间的关系程度。 O（2）仍然是恒定时间，所以我们只是将其近似为O（1），因为它意味着或多或less是相同的东西。
实际上，只有一种方法可以用O（1）来创build一个“完美的哈希表”，这就需要：
- 全球完美的哈希密钥生成器
- 一个无界的寻址空间。
（ 例外情况 ：如果您可以预先计算系统允许的所有密钥的排列，并且您的目标后台存储地址空间被定义为可容纳所有允许的密钥的大小，那么您可以拥有一个完美的散列，但它的“域限”完美）
给定一个固定的内存分配，这样做是不合理的，因为它会假设你有一些不可思议的方法来将无限的数据量打包到一个固定的空间中，而不会丢失数据，这在逻辑上是不可能的。
所以回顾性地说，获得O（1.5）仍然是一个恒定的时间，在一个有限的内存中，即使是一个相对朴素的哈希密钥生成器，我也认为该死的真棒。
附注请注意我在这里使用O（1.5）和O（2）。 这些实际上并不存在于大o。 这些仅仅是那些不了解的人所认为的大概是理由。
如果有1.5个步骤find一个键，或2个步骤find该键，或1个步骤find该键，但步数从未超过2，是否需要1步或2是完全随机的，那么它仍然是O的大O（1）。 这是因为不pipe添加到数据集大小的项目有多less，它仍然保持<2个步骤。 如果对于所有的表> 500个键需要2个步骤，那么你可以假设这2个步骤实际上是一步与2个部分，…仍然是O（1）。
如果你不能做这个假设，那么你根本就不是大O思维，因为那么你必须使用代表完成所有事情所需的有限的计算步骤的数量的数字，对你来说“一步”是毫无意义的。 只要进入你的脑海，Big-O与所涉及的执行周期之间就没有直接的关系。
我认为，当许多人抛弃“O（1）”这个词时，他们隐含的是一个“小”的常数，无论“小”是什么意思。
你必须根据上下文和常识来进行所有的大O分析。 它可以是一个非常有用的工具，也可能是荒谬的，取决于你如何使用它。
