2012-05-12 65 views

回答

5

散列實現了以破壞秩序爲代價的恆定時間搜索。當我搜索元素,我哈希它(O(1)),並在選定的水桶看看(O(n)在最壞的情況下,如果我掃描線,所有其他的桶可能是空的。)

當我想下一個元素在給定之後,我不能保證它會在同一個桶中。事實上,我根本不知道它在哪裏。由於我不知道接班人是什麼,我不能哈希它找到它的桶。相反,我被迫看在每個桶(O(m)。)

如果我爲了探測項目掃描桶的時候,我最終也做了總的線性工作中的項目(O(n))的數量。這導致總複雜度爲O(n + m)