「線形探索」の版間の差分
表示
削除された内容 追加された内容
Luckas-bot (会話 | 投稿記録) m r2.7.1) (ロボットによる 追加: hy:Գծային փնտրում/Ավազաարկղ |
Luckas-bot (会話 | 投稿記録) m r2.7.1) (ロボットによる 追加: hy:Գծային փնտրում |
||
62行目: | 62行目: | ||
[[en:Linear search]] |
[[en:Linear search]] |
||
[[fi:Peräkkäishaku]] |
[[fi:Peräkkäishaku]] |
||
[[hy:Գծային փնտրում |
[[hy:Գծային փնտրում]] |
||
[[id:Pencarian linear]] |
[[id:Pencarian linear]] |
||
[[is:Línuleg leit]] |
[[is:Línuleg leit]] |
2012年3月22日 (木) 13:04時点における版
リストや配列に入ったデータに対する検索を行うにあたって、 先頭から順に比較を行い、それが見つかれば終了する。
個のデータから個のデータを検索する場合、 時間計算量は、空間計算量は必要となる。
アルゴリズムの流れ
下のような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
grep /REGEXP/, @list;
Python
def search(list, x):
return x in list
Common Lisp
(defun linear-search (list x)
(labels ((spam (ls)
(and (consp ls)
(or (zerop (- (car ls) x))
(spam (cdr ls))))))
(spam list)))