Jak*_*ake 1 algorithm big-o hashtable time-complexity
在Skiena的算法设计书中,假设哈希表可以有最大的m桶和元素的总数n,则会观察到以下更糟糕的案例时间复杂性:
搜索: O(n)
接班人: O(n + m)
为什么两者不同？在某种程度上找不到继承者还涉及搜索下一个元素？
Hashing以破坏秩序为代价实现了恒定时间搜索.当我搜索一个元素时,我将它哈希(O(1))并查看所选的桶(O(n)在最坏的情况下,如果我线性扫描,因为所有其他桶可能都是空的.)
当我想要一个给定的元素之后的下一个元素时,我不能保证它将在同一个桶中.事实上,我根本不知道它在哪里.由于我不知道继承者是什么,我不能哈希它找到它的桶.相反,我被迫查看每个桶(O(m).)
如果我在扫描铲斗时按顺序探测物品,我最终也会在物品数量(O(n))中完成线性工作.这导致了总的复杂性O(n + m).