hashtable - クローズドハッシュアルゴリズムの時間計算量

Question

(4、2、12、3、9、11、7、8、13、および 18) に近接ハッシュアルゴリズムを適用したとします。また、ハッシュ テーブルの長さは最初は7であるとします。最悪の場合、そのようなハッシュ テーブルの検索をO(1)時間で達成する方法。

Answer 1

あなたが何をするかは本当に問題ではありません。データセットは事前に決定されているため、ハッシュ関数の最悪の場合のルックアップには一定の上限があります (ハッシュ関数が終了することが保証されている限り)。(1 つの要素を他の要素よりも見つけるのに時間がかかる場合、それが上限です。) 一定の上限は、O(1) の複雑さを意味します。QED。