線型探索
出典: フリー百科事典『ウィキペディア（Wikipedia）』
リストや配列に入ったデータに対する検索を行うにあたって、先頭から順に比較を行い、それが見つかれば終了する。
個のデータから
個のデータを検索する場合、時間計算量は
、空間計算量は
必要となる。
目次 |
アルゴリズムの流れ
下のような7個のデータを持つリストがある。このときに今要素1がどこにあるか、検索したい。
| 10 | 7 | 12 | 6 | 1 | 4 | 3 |
線形探索では、
- 最初の要素である10を見る。
- 10は1ではないので、次の要素7を見る。
- 7は1ではないので、次の要素12を見る。
- 12は1ではないので、次の要素6を見る。
- 6は1ではないので、次の要素1を見る。1を見つけることができた。
最悪のケースは、このリストの場合、要素3を見つけるときで、7個のデータ全てを見ないと、見つけることができない。つまり、n個のデータから1個のデータを検索する場合に最悪
の計算時間を要することとなる。
プログラム例
Perl
<source lang="perl">grep /REGEXP/, @list;</source>
Python
<source lang="python">def search(list, x):
return x in list
</source>
Common Lisp
<source lang="lisp">(defun linear-search (list x)
(labels ((spam (ls) (and (consp ls) (or (zerop (- (car ls) x)) (spam (cdr ls)))))) (spam list)))
</source>
関連項目
Une fenêtre (pop-into) d'information (contenu principal de Sensagent) est invoquée un double-clic sur n'importe quel mot de votre page web. LA fenêtre fournit des explications et des traductions contextuelles, c'est-à-dire sans obliger votre visiteur à quitter votre page web !