2 解決したい問題

英単語のデータベースを作ることを考える．表1のようにスペルと和訳の 組があり，探索(サーチ)と削除，追加ができるようにする．もちろん，これはコンピュー ターのメモリー上で実現させるのである．

表 1: 単語データベース

スペル	和訳
orange	みかん
apple	リンゴ
peach	桃
pineapple	パイナップル
pear	梨
grape	ぶどう
$\vdots$	$\vdots$

図 1: データはメモリーに入れる

単語は，スペルと和訳が組になっている．このような場合，構造体を使うのが常套手段で ある．複数の単語を表す単純なデータ構造として，教科書 [1] では以下の2つの方法が示されている．

• リスト
• 配列

リストを探索する場合，必ず先頭から順番に調べる．そのため，予めソートしても探索ス ピードは変わらない．したがって，ソートする必要がなく，データの追加はリストの末尾 に接続することになる．このような場合，探索には$O(N)$ ，削除には$O(N)$ ,追加には $O(N)$ の計算量が必要となる．実際，ソートすると実行スピードは変わるが，オーダーは 変わらないことに注意しよう．

配列の場合，バイナリーサーチが使えるので，予めソートしておくと探索スピードを向上 させることができる．しかし，データの追加と削除を行う場合，配列の入れ替えが必要と なり，そこでの計算量が増加する．この場合，探索には $O(\log_2 N)$ ，削除には$O(N)$ ， 追加には$O(N)$ の計算量が必要となる．ソートしない配列の場合，計算量のオーダーはリ ストと変わらない．

まとめると，表2のようになる．いずれにしても，データ数$N$ が 大きくなると，かなりの計算量が必要となる．

表 2: 計算量のオーダー

方法	探索	削除	追加
リスト	$O(N)$	$O(N)$	$O(N)$
ソートされた配列	$\log_2 N$	$O(N)$	$O(N)$

リストや配列を使うと$O(N)$ のオーダーの計算量が必要になってくる．もう少し，スピード アップしたい場合，マップというものが使われる．通常は，

• 「2分木」をつかった「ツリーマップ」
• 「ハッシュ表」をつかった「ハッシュマップ」

が使われる．
ホームページ: Yamamoto's laboratory
著者: 山本昌志