O（1）是什么？ [英] What's Up with O(1)?
问题描述
基本上，O（1）意味着由固定时间和（通常）固定空间界定。一些相当基础的操作是O（1），虽然使用中间语言和特殊VM倾向于扭曲这里想的（例如，如何一个摊分垃圾收集器和其他动态过程，否则O（1）活动） / p>
但是忽略延迟的延迟，垃圾收集等等，我还是不明白如何跳跃的假设某些技术，涉及某种搜索可以除非在非常特殊的条件下。
虽然我注意到了这个，一个例子刚刚出现在。
正如我在那里所说，我知道的唯一集合提供O（1）访问作为保证绑定是具有整数索引值的固定绑定数组。假定该数组是通过一些映射到随机存取存储器来实现的，该随机存取存储器使用O（1）操作来定位具有该索引的单元。
排序搜索以确定不同种类的索引（或对于具有整数索引的稀疏数组）的匹配单元格的位置，生活不那么容易。特别地，如果存在collisons并且拥塞是可能的，则访问不完全是O（1）。如果集合是灵活的，则必须识别和摊销扩展用于的底层结构（例如树或散列表）的成本，其中拥塞缓解（例如，高碰撞发生率或树不平衡） 。
我永远不会想到这些灵活和动态的结构如O（1）。然而，我看到他们提供了O（1）解决方案，没有任何确定必须保持实际有O（1）访问保证条件（以及该常数可以忽略不计）。
问题：这个准备真的是一个问题。 O（1）周围的随意性是什么？为什么它被盲目接受？是否认识到即使O（1）可能不合需要地大，即使接近常数吗？或者是O（1）简单地将计算复杂性概念用于非正式使用？我很困惑。
更新：答案和评论指出，我是偶然的定义O（1）自己，我已经修复了。我仍然在寻找好的答案，在一些情况下，一些评论主题比他们的答案更有趣。
我的理解是O（1）不一定是常数;相反，它不依赖于所考虑的变量。因此，散列查找可以被称为相对于散列中的元素的数量的O（1），而不是相对于散列的数据的长度或元素与散列中的桶的比率。
另一个混乱的原因是大O记法描述了限制行为。因此，对于小值N的函数f（N）确实可以显示出很大的变化，但是如果N近于无穷大的限度相对于N是常数，则仍然是正确的说是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.
My understanding is that O(1) is not necessarily constant; rather, it is not dependent on the variables under consideration. Thus a hash lookup can be said to be O(1) with respect to the number of elements in the hash, but not with respect to the length of the data being hashed or ratio of elements to buckets in the hash.
The other element of confusion is that big O notation describes limiting behavior. Thus, a function f(N) for small values of N may indeed show great variation, but you would still be correct to say it is O(1) if the limit as N approaches infinity is constant with respect to N.
这篇关于O（1）是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
