O（1）怎么办？(What's Up with O(1)?)

 我一直在注意到O（1）在讨论涉及散列和搜索类型的算法时，通常在使用语言系统提供的字典类型的上下文中，或者使用使用数组的字典或散列数组类型的一些非常奇怪的用法指标符号 
 
 基本上，O（1）表示由固定时间和（通常）固定的空间限定。 一些相当基本的操作是O（1），尽管使用中间语言和特殊的虚拟机往往会扭曲这里的思考（例如，如何将垃圾收集器和其他动态过程分摊到另外的O（1）活动）。 
 
 但忽略延迟，垃圾收集等的摊销，我仍然不明白如何跨越式的假设，某些涉及某种搜索的技术可以是O（1），除非是非常特殊的条件。 
 
 虽然我以前注意到这个例子，但是在Pandincus问题中出现了一个例子，“在C＃.NET中使用O（1）时间获得项目的”正确“集合？ 。 
 
 正如我在那里所说，我所知道的唯一的集合是提供O（1）访问作为保证绑定是具有整数索引值的固定绑定数组。 假设数组通过一些映射到使用O（1）操作来定位具有该索引的单元的随机存取存储器来实现。 
 
 对于涉及某种搜索的集合来确定不同类型索引的匹配单元格的位置（或对于具有整数索引的稀疏数组），生命并不容易。 特别是，如果有碰撞和拥塞是可能的，访问不完全是O（1）。 如果收集是灵活的，则必须识别和摊销扩展基础结构（如树或哈希表）的成本， 
 
   从而 
 阻塞（例如高碰撞发生率或树不平衡）。 
 
 我永远不会想到这些灵活和动态的结构如O（1）。 然而，我看到他们提供了O（1）个解决方案，而没有任何确定必须保持的条件，实际上可以保证O（1）访问（以及这个常数可以忽略不计）。 
 
 问题：所有这些准备工作真的是一个问题。 O（1）周围的休闲是什么，为什么会盲目接受？ 是否认识到即使O（1）可以不合需要地大，即使接近常数？ 或者O（1）只是将计算复杂性的概念用于非正式使用？ 我很困惑 
 
 更新：答案和评论指出我自己在哪里定义O（1），我已经修复了。 我仍然在寻找好的答案，有些评论主题比他们的答案更有趣，在一些情况下。 

I have been noticing some very strange usage of O(1) in discussion of algorithms involving hashing and types of search, often in the context of using a dictionary type provided by the language system, or using dictionary or hash-array types used using array-index notation.
 
Basically, O(1) means bounded by a constant time and (typically) fixed space. Some pretty fundamental operations are O(1), although using intermediate languages and special VMs tends to distort ones thinking here (e.g., how does one amortize the garbage collector and other dynamic processes over what would otherwise be O(1) activities).
 
But ignoring amortization of latencies, garbage-collection, and so on, I still don't understand how the leap to assumption that certain techniques that involve some kind of searching can be O(1) except under very special conditions.
 
Although I have noticed this before, an example just showed up in the Pandincus question, "'Proper’ collection to use to obtain items in O(1) time in C# .NET?".
 
As I remarked there, the only collection I know of that provides O(1) access as a guaranteed bound is a fixed-bound array with an integer index value. The presumption is that the array is implemented by some mapping to random access memory that uses O(1) operations to locate the cell having that index.
 
For collections that involve some sort of searching to determine the location of a matching cell for a different kind of index (or for a sparse array with integer index), life is not so easy. In particular, if there are collisons and congestion is possible, access is not exactly O(1). And if the collection is flexible, one must recognize and amortize the cost of expanding the underlying structure (such as a tree or a hash table) for 
 
   which 
  congestion relief (e.g., high collision incidence or tree imbalance).
 
I would never have thought to speak of these flexible and dynamic structures as O(1). Yet I see them offered up as O(1) solutions without any identification of the conditions that must be maintained to actually have O(1) access be assured (as well as have that constant be negligibly small).
 
THE QUESTION: All of this preparation is really for a question. What is the casualness around O(1) and why is it accepted so blindly? Is it recognized that even O(1) can be undesirably large, even though near-constant? Or is O(1) simply the appropriation of a computational-complexity notion to informal use? I'm puzzled.
 
UPDATE: The Answers and comments point out where I was casual about defining O(1) myself, and I have repaired that. I am still looking for good answers, and some of the comment threads are rather more interesting than their answers, in a few cases.

原文：https://stackoverflow.com/questions/332952