1
在Skiena's book of algorithm design,鑑於散列表可具有最大m
水桶和元件的總數是n
,下面更壞情況下的時間複雜性,觀察到:哈希表:搜索VS後繼時間複雜
搜索:O(n)
後繼:O(n + m)
爲什麼兩者不同?還沒有找到繼任者的方式涉及搜索下一個元素?
在Skiena's book of algorithm design,鑑於散列表可具有最大m
水桶和元件的總數是n
,下面更壞情況下的時間複雜性,觀察到:哈希表:搜索VS後繼時間複雜
搜索:O(n)
後繼:O(n + m)
爲什麼兩者不同?還沒有找到繼任者的方式涉及搜索下一個元素?
散列實現了以破壞秩序爲代價的恆定時間搜索。當我搜索元素,我哈希它(O(1)
),並在選定的水桶看看(O(n)
在最壞的情況下,如果我掃描線,所有其他的桶可能是空的。)
當我想下一個元素在給定之後,我不能保證它會在同一個桶中。事實上,我根本不知道它在哪裏。由於我不知道接班人是什麼,我不能哈希它找到它的桶。相反,我被迫看在每個桶(O(m)
。)
如果我爲了探測項目掃描桶的時候,我最終也做了總的線性工作中的項目(O(n)
)的數量。這導致總複雜度爲O(n + m)
。