リスト探索(list search)アルゴリズム

アルゴリズム探索アルゴリズム

概要

 状態:-  閲覧数:1,178  投稿日:2016-09-01  更新日:2016-09-03  
最も基本的な探索アルゴリズム

目的
・リストから何らかのキーを持つ要素を探すこと

3種類
A.線形探索
B.二分探索
C.内挿探索

A.線形探索

 閲覧数:249 投稿日:2016-09-03 更新日:2016-10-05 

最も単純なリスト探索アルゴリズム


リストや配列に入ったデータに対する検索を行う
・各要素を単純に先頭から調べ(比較し)ていく
・見つかれば終了
・どんなリストでも適用可能

n個のデータから m個のデータを検索する場合
・時間計算量 … O(nm)
・空間計算量 … O(1)
・実行時間 … O(n)

n
・リスト上のアイテム数


具体例


下記のような7個のデータを持つリストがある
10 7 12 6 1 4 3
普通のケース / 要素1がどこにあるか、検索したい
・最初の要素である10を見る
・10は1ではないので、次の要素7を見る
・7は1ではないので、次の要素12を見る
・12は1ではないので、次の要素6を見る
・6は1ではないので、次の要素1を見る
・1を見つけることができた

最悪のケース / 要素3がどこにあるか、検索したい
・7個のデータ全てを見ないと、見つけることができない

n個のデータから1個のデータを検索する場合
・最悪O(n)の計算時間を要する

B.二分探索 / バイナリサーチ

 閲覧数:292 投稿日:2016-09-12 更新日:2016-11-08 

より洗練されたリスト探索アルゴリズム


データが多ければ多いほど線型探索よりも性能がよくなるが
探索前にソートしておく必要がある
※同一データは無い前提

検索対象
・ソート済み配列
※大小関係を使用するため、「未ソートのリスト」や「大小関係の定義されない要素を含むリスト」には二分探索を適用することはできない

処理の流れ
・中央の値を見る
・検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断
・片側に存在しないことを確かめながら検索していく

n個のデータがある場合、
・時間計算量 … O(log2 n)
・実行時間 … O(log n)

n個のデータの「中央の値」を見ることで、
・1回の操作でn/2個程度(奇数の場合は(n-1)/2個、偶数の場合はn/2個または(n/2)-1個)の要素を無視することができる


データが見つかる具体例


下記配列から25を探し出す
・同一のデータは無い
位置 1 2 3 4 5 6 7 8 9 10
データ 1 3 4 11 12 13 17 22 25 28
1.、配列の中央位置を求める
・(1+10)/2=5 
(端数は切捨、切上のどちらでもいいが、ここは切捨とする。以下同じ)
・位置5のデータは12なので「×」
・位置1~4まではデータを調べなくても「×」と分かる。※予め昇順ソートしているため

2-1.残りの配列の中央位置を求める
・位置6~10の中央位置は、(6+10)/2=8
・位置8のデータは22なので「×」
・位置6~7まではデータを調べなくても「×」と分かる。※予め昇順ソートしているため

2-2.残りの配列の中央位置を求める
・位置9~10の中央の位置は、(9+10)/2=9
(端数は切捨、切上のどちらでもいいが、ここは切捨とする。以下同じ)
・位置9のデータは25なので目的のデータが見つかった
・位置10は調べていないが、同一のデータは存在しないという想定なので「×」としてよい



データが見つからない具体例1


下記配列から4を探し出す
・同一のデータは無い
位置 1 2 3 4 5 6 7 8 9 10
データ 1 3 5 11 12 13 17 22 25 28
1.、配列の中央位置を求める
・(1+10)/2=5 
・位置5のデータは12なので「×」
・位置6~10まではデータを調べなくても「×」と分かる。※予め昇順ソートしているため

2-1.残りの配列の中央位置を求める
・位置1~4の中央の位置は、(1+4)/2=2
・位置2のデータは3なので「×」
・位置1のデータは1なので「×」

2-2.残りの配列の中央位置を求める
・位置3~4の中央の位置は、(3+4)/2=3
・位置3のデータは5なので「×」
・以上でデータが見つからないという結果になる


データが見つからない具体例2


下記配列から29を探し出す
・同一のデータは無い
位置 1 2 3 4 5 6 7 8 9 10
データ 1 3 5 11 12 13 17 22 25 28
データの全体の一番右側が29より小さい
・データが見つからないという結果になる


C.内挿探索

 閲覧数:273 投稿日:2016-09-13 更新日:2016-11-08 

C.内挿探索


分布が偏っていないソートされた大きなリストでは二分探索よりも性能が良いが、最悪ケースでは O(n) となる





探索アルゴリズム

文字列探索

コメント投稿(ログインが必要)



類似度ページランキング
順位 ページタイトル抜粋
1 探索アルゴリズム 50
2 article 45
3 Chromecast 41
4 Apache Solr 40
5 Flash Video 40
6 アルゴリズム 40
7 stable build 39
8 latest build 39
9 Apache JMeter 38
10 Ordinal Scale 38
11 Hyper Estraier 37
12 git push 36
13 Morris-Pratt algorithm 35
14 Morris-Pratt algorithm border 34
15 activeCollab 33
16 Same-origin policy 33
17 Eclipse 32
18 K-means 法(K平均法) 31
19 Knuth–Morris–Pratt algorithm border 31
20 attribute 30
2022/12/04 1:05 更新