我想创建一个数据结构或集合,在添加、删除和计算 no 时复杂度为 O(1)。的元素。我应该如何开始?
我想到了一个解决方案:我将使用一个哈希表,对于插入的每个键/值对,我将只有一个哈希码,即:我的哈希码算法每次都会生成一个唯一的哈希值,因此存储值的索引将是唯一的(即没有冲突)。
这会给我 O(1) 复杂度吗?
最佳答案
是的,这会起作用,但正如您提到的,您的哈希函数需要 100% 唯一。任何重复都会导致您不得不使用某种冲突解决方案。我会推荐线性链接。
编辑 Hashmap.size() 允许 O(1) 访问
编辑 2: 对 Larry 造成的困惑的回应 =P
是的,散列是 O(k),其中 k 是 key 长度。每个人都可以同意这一点。但是,如果您没有完美的散列,您根本无法获得 O(1) 时间。你的主张是你不需要唯一性来实现 O(1) 删除特定元素。我向你保证那是错误的。
考虑一个最坏的情况:每个元素散列到相同的东西。你最终得到一个链表,众所周知,它没有 O(1) 删除。我希望,正如您提到的,没有人愚蠢到像这样制作哈希。
要点是,哈希的唯一性是 O(1) 运行时间的先决条件。
即便如此,从技术上讲,它也不是 O(1) 大 O 效率。只有使用摊销分析,您才能在最坏的情况下实现恒定的时间效率。正如维基百科关于摊销分析的文章所述
The basic idea is that a worst case operation can alter the state in such a way that the worst case cannot occur again for a long time, thus "amortizing" its cost.
这指的是在某些负载因子下调整哈希表的大小(改变数据结构的状态)可以确保更小的冲突机会等。
我希望这一切都清楚了。
关于algorithm - 如何创建复杂度为 O(1) 的集合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3353052/