我正在试着和一位朋友一起做作业，一个问题是询问用于线性探测方法的搜索，添加和删除的平均运行时间。 我认为它是O（n），因为它必须检查一定数量的节点，直到它找到一个打开的节点为止。 搜索时，它从原始索引处开始并向上移动，直到找到所需的数字。 但我的朋友说这是O（1）。 哪一个是对的？
最满意答案
当我们谈论渐近复杂性时，我们通常会考虑非常大的n。 现在，对于哈希表中的碰撞处理，一些方法是链接哈希和线性探测。 在这两种情况下，可能发生两件事情（这将有助于回答您的问题）：1.您可能需要调整散列表的大小，因为它已满。2.可能会发生冲突。
在最糟糕的情况下，它将取决于你如何实现你的散列表，比如在线性探测中你找不到数字，你继续移动并且你要查找的数字到最后。 这是O（n）最坏情况下的运行时间。 即将发生链接散列技术时，发生冲突时，处理它们时说我们已将密钥存储在平衡二叉树中，因此最坏情况下的运行时间为O（log n）。
现在来看最好的情况下，我认为没有混淆，无论哪种情况，它都是O（1）。
O（n）会发生在最坏的情况下，而不是一个设计良好的散列表的平均情况。 如果这种情况在平均情况下散列表开始发生不会在数据结构中找到一个位置，因为平均而言，平衡树会始终给您O（log n），并且ON TOP OF THAT也会保留该顺序。
很抱歉说这个，但不幸的是你的朋友是对的。 你的情况会发生在最坏的情况下。
还可以在这里查看更多信息，例如分期运行时间： 哈希表的时间复杂度
转：https://www.656463.com/wenda/slpzxxtcyxsj_118
标签：最坏,列表,情况,哈希,线性,探测 From： https://www.cnblogs.com/blogzero/p/17435696.html