探索問題

質問

ｎ個のデータがあり，その中から与えられたキー
を持つデータを探索するとき,最大計算時間の下界が
Ω(log ｎ)であることを証明したいのですが,どうしても
わかりません．どのようにしたらよいかどなたか教えて
下さい．よろしくお願いします．

回答No.2

yfujii · ベストアンサー

ｎ個のデータの並び方によると思います。データを並べる時ハッシュ関数で検索できるように入れるかインデックスを付けておけばデータの検索はＯ(1)です。

非常に便利な検索法なので下記単語でインターネット検索すればたくさん出てきますので探して下さい。
ハッシュ　Ｏ　検索

回答No.1

επιστημη（@episteme）

n個のデータがデタラメにならんでいたら、先頭から順に調べるしかないのだから時間計算量はΟ(n)ですけど。

前提がまちがっていませんか?

昇順に並んでいたら二分検索によってΟ(log n)となります。