当操作“接近O（1）”时，意味着什么与“是O（1）”相反 [英] What does it mean when an operation "approaches O(1)" as opposed to "is O(1)"?

问题描述

考虑例如.NET Framework 4.5的文档 Dictionary< TKey，TValue> class：

在的备注中。包含Key 方法，他们声明

此方法接近O（1）操作。

而且在备注对于 .Count 属性，他们声明

检索这个属性是一个O（1）操作。

请注意，我不会要求详细信息的 C＃， .NET ，字典或大O符号一般。我刚刚发现这种区分方法有趣。

有什么区别吗？如果是这样，它可能有多重要？我应该注意吗？

解决方案

如果哈希码中的底层对象使用的哈希函数是好的意味着碰撞将非常罕见。奇怪的是，在给定的哈希桶中只有一个项目，也许是两个，几乎没有更多。如果可以肯定地说，永远不会超过 c 项目（其中 c 是一个常量）在桶中，则操作将为O（c）（其为O（1））。但是这种保证是不可能的。可能，你只是碰巧有不同的项目，不幸的是，所有的冲突，并且都在同一个桶中，在这种情况下， ContainsKey 是O（n）。哈希函数也可能不是很好，并且会导致哈希冲突频繁，这使得实际包含的检查比O（1）更糟。

Consider for example the documentation for the .NET Framework 4.5 Dictionary<TKey, TValue> class:

In the remarks for the .ContainsKey method, they state that

This method approaches an O(1) operation.

And in the remarks for the .Count property, they state that

Retrieving the value of this property is an O(1) operation.

Note that I am not necessarily asking for the details of C#, .NET, Dictionary or what Big O notation is in general. I just found this distinction of "approaches" intriguing.

Is there any difference? If so, how significant can it potentially be? Should I pay attention to it?

解决方案

If the hash function used by the underlying objects in the hash code is "good" it means collisions will be very rare. Odds are good that there will be only one item at a given hash bucket, maybe two, and almost never more. If you could say, for certain, that there will never be more than c items (where c is a constant) in a bucket, then the operation would be O(c) (which is O(1)). But that assurance can't be made. It's possible, that you just happen to have n different items that, unluckily enough, all collide, and all end up in the same bucket, and in that case, ContainsKey is O(n). It's also possible that the hash function isn't "good" and results in hash collisions frequently, which can make the actual contains check worse than just O(1).

这篇关于当操作“接近O（1）”时，意味着什么与“是O（1）”相反的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！