用n個元素初始化散列表的運行時間是什麼？

Question

是O（n）還是O（n logn）？我有n個需要在哈希表中設置的元素，什麼是最壞情況和平均運行時間？

Answer 1

最壞的情況是無限的。您需要計算哈希代碼，並且可能需要比較元素，並且時間不限。

假設計算哈希和比較元素是恆定時間，插入最壞的情況是O（n^2）。實際上，最糟糕的情況會非常罕見，假設中途體面有功能，那麼可以節省您的是什麼。體面實施的平均時間是O（n）。