Pythonで線形探索。計算量と実際の計算時間をみてみる。

はじめに

Pythonによる線形探索の実装になります。実際の計算時間もグラフで出力しています。

また、線形探索よりも優秀な検索アルゴリズムである、二分探索はこちらです。二分探索の記事で、線形探索との比較ものせています。

Pythonで二分探索。時間計算量と実際の計算時間をみてみる。

目次

線形探索とは？

線形探索(linear search)とは、検索アルゴリズムの一つです。 リストに入っているデータの検索を行います。 その方法はシンプルで、先頭から順に比較を行い、一致した時点で終了となります。

線形探索の時間計算量

線形探索は先頭から順に比較を行う為、時間計算量はとなります。 末尾に近づけば近づくほど、線形的に計算時間が増加します。

Pythonによる線形探索の実装例

Pythonによる線形探索の実装例となります。リストは0から順に値が代入されているとします。

list = range(100) # [0, 1, 2...99]
target = 3

for n in list:
    if (n == target):
        break # 検索が一致した

Pythonによる線形探索の実際の計算時間

こちらが10万のリストにたいして、実際にPythonで線形探索を行ったときのグラフとなります。末尾に近ければ近いほど、線形的に計算時間が増加していくのがわかります。