哈希碰撞線性探測運行時間

我正在嘗試與一位朋友做功課，一個問題詢問了線性探測方法的搜索，添加和刪除的平均運行時間。我認爲它是O（n），因爲它必須檢查一定數量的節點，直到它找到一個打開的節點爲止。搜索時，它從原始索引處開始並向上移動，直到找到所需的數字。但我的朋友說這是O（1）。哪一個是對的？哈希碰撞線性探測運行時間

來源

2012-04-09 Richard

我想添加到Yavar答案：記住，O（1）不是一個運算。它可能是一個很大的常量，但是，如果它不是來自像n這樣的變量，那並不重要。即使你需要通過20個節點來放置一個散列，它仍然是一個O（1）。當然，這適用於哈希表只有當某些條件爲真，但求好設計的哈希表是O（1）平均 – Archeg 2012-04-09 11:51:38

當我們談論漸近複雜性時，我們通常會考慮非常大的n。現在對於哈希表中的碰撞處理，一些方法是鏈式哈希&線性探測。在這兩種情況下，可能發生兩件事情（這將有助於回答您的問題）：1.您可能需要調整散列表的大小，因爲它已滿。2.可能會發生衝突。

在這將取決於你如何執行你的哈希表最壞的情況下，例如在線性探測你不找數，你繼續移動，你要找的數量在年底。這是O（n）最壞情況下的運行時間。即將發生鏈接散列技術時，發生衝突時，處理它們時說我們已將密鑰存儲在平衡二叉樹中，因此最壞情況下的運行時間爲O（log n）。

現在即將到達最佳運行時間，我認爲沒有混淆，在任何情況下它都是O（1）。 O（n）會在最壞的情況下發生，而不是在設計良好的散列表的平均情況下發生。如果開始在平均情況哈希表發生不會找到數據結構的地方，因爲上平均再平衡樹會給你O（log n）的總是和上TOP將保留階也。

很抱歉這麼說，但不幸的是你的朋友是對的。你的情況會發生在最壞的情況下。

也看看這裏的信息更豐富的東西即攤銷運行時間：Time complexity of Hash table

來源

2012-04-09 11:34:37 Yavar

感謝@DanAllen，您的評論上述真的激勵:) – Yavar 2014-12-16 19:46:24

哈希碰撞線性探測運行時間

回答

相關問題