Ric*_*ard 8 algorithm hashtable asymptotic-complexity data-structures
我正在尝试与朋友做作业,一个问题询问线性探测方法的搜索,添加和删除的平均运行时间.我认为它是O(n)因为它必须检查特定数量的节点,直到它找到一个要添加的开放节点.当搜索它从原始索引开始并向上移动直到找到所需的数字.但我的朋友说这是O(1).哪一个是对的？
Yav*_*var 10
当我们谈论渐近复杂性时,我们通常会考虑非常大的n.现在,对于哈希表中的冲突处理,一些方法是链式散列和线性探测.在这两种情况下,可能会发生两件事情(这将有助于回答您的问题):1.您可能需要调整哈希表的大小,因为它已满2.冲突可能发生.
在最坏的情况下,它将取决于你如何实现你的哈希表,比如线性探测,你没有找到数字,你继续移动,你正在寻找的数字是在最后.这是O(n)最坏情况下的运行时间.进行链式散列技术,当发生碰撞时,处理它们说我们已将密钥存储在平衡二叉树中,因此最坏情况下的运行时间将为O(log n).
现在来看最好的案例运行时间,我认为没有混乱,在任何一种情况下它都是O(1).
O(n)将在最坏的情况下发生,而不是在设计良好的哈希表的平均情况下.如果在平均情况哈希表中开始发生这种情况,则不会在数据结构中找到一个位置,因为平均而言平衡树将总是给你O(log n),并且ON TOP OF THAT也会保留订单.
很抱歉这样说但不幸的是你的朋友是对的.你的情况会发生在最坏的情况下.
还可以在这里查看更多信息,即摊销的运行时间:哈希表的时间复杂度