カテゴリー:
探索アルゴリズム
閲覧数:324 配信日:2016-09-03 10:14
最も単純なリスト探索アルゴリズム
リストや配列に入ったデータに対する検索を行う
・各要素を単純に先頭から調べ（比較し）ていく
・見つかれば終了
・どんなリストでも適用可能
n個のデータから m個のデータを検索する場合
・時間計算量 … O(nm)
・空間計算量 … O(1)
・実行時間 … O(n)
n
・リスト上のアイテム数
具体例
下記のような7個のデータを持つリストがある
| 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個のデータを検索する場合
・最悪O(n)の計算時間を要する