Dav*_* S. 8 .net c# optimization big-o
例如,考虑.NET Framework 4.5 Dictionary<TKey, TValue>类的文档:
在该方法的评论中.ContainsKey,他们说明了这一点
该方法接近O(1)操作.
在财产的评论中.Count,他们说明了这一点
检索此属性的值是O(1)操作.
请注意,我不是一定要求的细节C#,.NET,Dictionary或者是什么大O符号是一般.我刚刚发现这种"方法"的区别很有趣.
有什么区别吗？如果是这样,它可能有多重要？我应该注意它吗？
Ser*_*rvy 10
如果哈希码中的底层对象使用的哈希函数是"好的",则意味着冲突将非常罕见.可能性很大,在给定的哈希桶中只有一个项目,可能是两个,几乎从不多.如果您可以肯定地说,在一个存储桶中永远不会有超过c项目(其中c是常量),那么操作将是O(c)(即O(1)).但这种保证是无法做到的.有可能,你碰巧有n个不同的项目,不幸的是,所有项目都会发生碰撞,并且最终都在同一个桶中,在这种情况下,ContainsKey就是O(n).散列函数也可能不是"好"并且经常导致散列冲突,这可能使实际包含检查比仅仅O(1)更差.
| 归档时间： |
|
| 查看次数： |
2383 次 |
| 最近记录： |