2023.12.28

線形検索アルゴリズム：配列内の要素を見つける方法

marugotoyoten

cs50のYoutube動画「線形検索アルゴリズム：配列内の要素を見つける方法」について要点と要約をまとめました

３つの要点

要点１
線形検索アルゴリズムの要点：アルゴリズムの手順、配列内の要素を見つける方法
要点２
線形検索の特徴：要素が存在しない場合でも機能する、最悪と最良の場合の計算量
要点３
線形検索の利点：シンプルで直感的な方法、要素の存在を確認できる

要約

線形検索アルゴリズムの仕組みはどのようなものですか？
線形検索アルゴリズムは、配列内の要素を見つけるためのステップバイステップの手順です。配列を左から右に反復処理し、各要素を指定された要素と比較します。一致する要素が見つかった場合、検索は停止します。それ以外の場合、要素が見つかるか、配列全体が走査されるまでプロセスは続きます。

線形検索は配列内に存在しない要素も見つけることができますか？
はい、線形検索は要素が配列内に存在しない場合でも機能します。アルゴリズムは各要素をチェックするプロセスを繰り返し、配列全体が調べられるまで続けます。すべての要素を調べた後に要素が見つからない場合、要素が配列に存在しないと結論付けることができます。したがって、線形検索は要素が存在しない場合でも成功します。

線形検索の計算量
線形検索の最悪の場合は、ターゲット要素が配列の最後の要素であるか、配列内に存在しない場合です。この場合、アルゴリズムはすべての要素を調べる必要があり、時間計算量はOになります。一方、最良の場合は、要素が配列の先頭で直ちに見つかる場合であり、時間計算量はomegaになります。

まとめ
線形検索アルゴリズムは、配列内の要素を見つけるためのシンプルで直感的な方法です。配列を反復処理し、各要素を目標の要素と比較します。線形検索は、要素が配列に存在する場合は要素を正常に見つけることができ、存在しない場合はそれを判断することができます。線形検索の時間計算量は、要素の位置によって異なり、最悪の場合はすべての要素を調べる必要があり、最良の場合は要素を直ちに見つけることができます。

▼今回の動画