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

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

概要

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

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

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

A.線形探索

 閲覧数:210 投稿日: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.二分探索 / バイナリサーチ

 閲覧数:254 投稿日: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.内挿探索

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

C.内挿探索


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





探索アルゴリズム

文字列探索

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



類似度ページランキング
順位 ページタイトル抜粋
1 探索アルゴリズム 50
2 article 45
3 Chromecast 41
4 Flash Video 40
5 アルゴリズム 40
6 Apache Solr 40
7 stable build 39
8 latest build 39
9 Ordinal Scale 38
10 Apache JMeter 38
11 Hyper Estraier 37
12 Morris-Pratt algorithm 35
13 Morris-Pratt algorithm border 34
14 activeCollab 33
15 Same-origin policy 33
16 Eclipse 32
17 K-means 法(K平均法) 31
18 Knuth–Morris–Pratt algorithm border 31
19 attribute 30
20 Hibernate 30
2022/7/03 2:34 更新
週間人気ページランキング / 6-26 → 7-2
順位 ページタイトル抜粋 アクセス数
1 ベクトル | 数学 | プログラミング用語 268
1 curl | HTTPクライアント(ネットワーク) | プログラミング用語 268
2 ルーター | ネットワーク | プログラミング用語 267
3 Flash Video | コンテナフォーマット | プログラミング用語 265
4 正規表現 | プログラミング | プログラミング用語 261
5 デーモン | Linux | プログラミング用語 258
6 ユースケース | 開発 | プログラミング用語 237
7 チェックアウト | バージョン管理システム(開発) | プログラミング用語 158
8 YouTube | API | プログラミング用語 128
9 Linux | プログラミング用語 45
10 PowerShell | スクリプト | プログラミング用語 44
11 可搬性 | プログラミング | プログラミング用語 33
12 クローラ | 検索エンジン | プログラミング用語 25
13 Subversion | バージョン管理システム(開発) | プログラミング用語 23
14 アンチパターン | プログラミング | プログラミング用語 11
15 プログラミング用語 9
16 deflate | ネットワーク | プログラミング用語 8
17 Nginx / Nginxとは?/ Apacheとの違い | プログラミング用語 6
17 YouTubeに掲載されている動画を、ユーザーが作成したWebサービス上で再生する方法 | プログラミング用語 6
17 WebLogic | アプリケーションサーバ(サーバ) | プログラミング用語 6
2022/7/3 1:01 更新