[計算量をざっくり理解] 線形探索の計算量

線形探索とは

線形探索（せんけいたんさく、英: linear search, sequential search）は、検索のアルゴリズムの一つ。リストや配列に入ったデータに対する検索を行うにあたって、先頭から順に比較を行い、それが見つかれば終了する。
出典: フリー百科事典『ウィキペディア（Wikipedia）』

ソートされていない配列の中でデータを探索する場合、配列の先頭から順に値を比較していきます。

入力サイズは、「配列の中のデータの数」になります。

例えば以下のような配列を考えます。

入力サイズは7です。探索は配列の左側から順に行うとします。

最善の場合（best case）

「１０」を探索する場合、一番最初に見つかります。これは線形探索の「最善の場合（best case）」で、入力サイズとは無関係に、計算量は\(O (1) \) となります。

最悪の場合（worst case）

逆に「最悪の場合（worst case）」は、例えば「0」を探索する場合で、左側から探索を行っていって最終的に見つかりません。計算量は\(O (n) \) となります。入力サイズが倍になれば、計算量も倍になります。

平均の場合（average case）

「平均の場合（average case）」の計算量を考えます。

配列のデータは一様に分布しているとすると、平均すれば\(2 / N \) 回の探索でデータを探索できると考えられます。漸近的に考えると、計算量は\(O (n) \) となります。

Python で線形探索を書いてみます。

nums = [10, 7, 12, 1, 6, 4, 3]

# index が分かっていれば、O(1) でデータにアクセスできる。
print(nums[3])

# for ループの中に O(1) の処理があるので、O(n)。
# forループ
for index in range(len(nums)):
    # O(1)
    if nums[index] == 1:
        print(index)