例如，考虑 .NET Framework 4.5Dictionary<TKey, TValue>类的文档：
在该方法的注释中.ContainsKey，他们指出
此方法接近 O(1) 操作。
在该物业的备注中.Count，他们指出
检索此属性的值是 O(1) 操作。
请注意，我不一定要询问C#,或 Big O 符号的一般细节。我只是发现这种“方法”的区别很有趣。.NETDictionary
有什么区别吗？如果是这样，它可能有多重要？我应该注意它吗？
问问题
2992 次
4 回答
10
如果散列码中底层对象使用的散列函数是“好”的，则意味着冲突将非常罕见。很有可能在给定的哈希桶中只有一个项目，也许两个，而且几乎永远不会更多。如果你可以肯定地说，一个桶中永远不会有多个c项目（其中c是一个常数），那么操作将是 O(c)（即 O(1)）。但不能做出这样的保证。有可能，你碰巧有 n 个不同的项目，不幸的是，它们都发生了碰撞，最终都在同一个桶中，在这种情况下，ContainsKey是 O(n)。哈希函数也可能不是“好”并且经常导致哈希冲突，这可能会使实际的包含检查比 O(1) 更糟糕。
于 2013-11-14T21:58:46.800 回答
4
这是因为 Dictionary 是哈希表的实现——这意味着通过使用哈希函数完成键查找，该函数告诉您数据结构中包含的许多存储桶中的哪个存储桶包含您正在查找的值。通常，对于一个好的散列函数，假设有足够大的桶集，每个桶只包含一个元素——在这种情况下，复杂度确实是 O(1)——不幸的是，这并不总是正确的——散列函数可能有冲突，在这种情况下，存储桶可能包含多个条目，因此算法必须遍历存储桶，直到找到您要查找的条目 - 因此对于这些（希望如此）罕见的情况不再是 O(1)。
于 2013-11-14T22:03:49.297 回答
0
O(1) 是一个恒定的运行时间，接近 O(1) 接近恒定但不完全是，但对于大多数目的来说，增加可以忽略不计。你不应该注意它。
于 2013-11-14T21:51:41.570 回答
0
有些东西要么是 O(1)，要么不是 O(1)。我认为他们想说的是，对于大量操作，每次操作的运行时间大约为 O(1)。
于 2013-11-14T21:53:10.410 回答