|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 線形 : [せんけい] 【名詞】 1. (1) line 2. straight alignment 3. (2) (gen) (math) linear ・ 形 : [けい, かたち, ぎょう] 1. (suf) shape 2. form 3. type ・ 探索 : [たんさく] 1. (n,vs) search 2. hunt 3. (item of) research 4. exploration 5. investigation ・ 索 : [さく] 【名詞】 1. rope 2. cord
線形探索(せんけいたんさく、)は、検索のアルゴリズムの一つ。 リストや配列に入ったデータに対する検索を行うにあたって、 先頭から順に比較を行い、それが見つかれば終了する。 個のデータから個のデータを検索する場合、 時間計算量は、空間計算量は必要となる。 ==アルゴリズムの流れ== 下のような7個のデータを持つリストがある。このときに今要素1がどこにあるか、検索したい。 線形探索では、 *最初の要素である10を見る。 *10は1ではないので、次の要素7を見る。 *7は1ではないので、次の要素12を見る。 *12は1ではないので、次の要素6を見る。 *6は1ではないので、次の要素1を見る。1を見つけることができた。 最悪のケースは、このリストの場合、要素3を見つけるときで、7個のデータ全てを見ないと、見つけることができない。 つまり、n個のデータから1個のデータを検索する場合に最悪の計算時間を要することとなる。 抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)』 ■ウィキペディアで「線型探索」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Linear search 」があります。 スポンサード リンク
|