🦝

「計算量（オーダー？）」って何？

2023/03/08に公開

Python

計算量（Complexity） とは、アルゴリズムの性能を客観的に評価するための尺度です。計算量は、時間計算量（Time Complexity：実行に要する時間を評価）と領域計算量（Space Complexity：実行に要する記憶域やファイル域を評価）の２つに大別することができます。

ここでは、線形探索と２分探索の時間計算量について考えてみます。

線形探索

線形探索は、リストの先頭から順番に探索対象を探していくメソッドになります。Python で記述した線形探索の例を以下に示します。

L = [1, 9, 2, 5, 4, 7]
def linear_search(search_obj):
    index = 0                     #1
    while index < len(L):         #2
        if L[index] == search_obj:#3
	    # 探索成功
	    return index          #4
	index += 1                #5
    # 探索失敗
    return -1                     #6

各ステップが実行される回数とその計算量を以下の表に示しています。
（ただし、探索するリストのサイズ： $len(L)$ を $n$ と表記しています。）

Step	実行回数（平均）	計算量
#1	1	$O(1)$
#2	$\frac{n}{2}$	$O(n)$
#3	$\frac{n}{2}$	$O(n)$
#4	1	$O(1)$
#5	$\frac{n}{2}$	$O(n)$
#6	1	$O(1)$

#1 は、最初だけ代入の処理を行うので、実行回数は 1 です。また、計算量も $O(1)$ になります（#4, #6 も同様の考え方です。）。#2, #3, #5 は、最大でリストの末尾まで検索する可能性があるので、実行回数の平均値は $\frac{n}{2}$ であり、 $n$ に比例した回数だけ実行される計算量は $O(n)$ と表します。

#1 から #6 で構成されるこのアルゴリズム全体の計算量は、各ステップでの計算量の最大値になります。つまり、この線形探索アルゴリズムは、 $O(1)$ と $O(n)$ で構成されているため、計算量は $O(n)$ になります。

２分探索

２分探索は、ソート済みのリストから探索範囲を半分に減らしながら探索するメソッドです。Python で記述した２分探索の例を以下に示します。

L = [1, 2, 4, 5, 7, 9]
def bin_search(search_obj):
    start = 0                     #1
    end = len(L) - 1              #2
    while True:                   #3
        mid = (start + end) // 2  #4
	if L(mid) == search_obj:  #5
	    # 探索成功
	    return mid            #6
        elif L[mid] < search_obj: #7
	    # 探索範囲を後半に絞り込む
	    start = mid + 1       #8
	else:
	    # 探索範囲を前半に絞り込む
	    end = mid - 1         #9
        if start > end:           #10
	    break
    # 探索失敗
    return -1                     #11

各ステップが実行される回数とその計算量を以下の表に示しています。
（ただし、探索するリストのサイズ： $len(L)$ を $n$ と表記しています。）

Step	実行回数	計算量
#1	1	$O(1)$
#2	1	$O(1)$
#3	$\log_2 n$	$O(\log_2 n)$
#4	$\log_2 n$	$O(\log_2 n)$
#5	$\log_2 n$	$O(\log_2 n)$
#6	1	$O(1)$
#7	$\log_2 n$	$O(\log_2 n)$
#8	$\log_2 n$	$O(\log_2 n)$
#9	$\log_2 n$	$O(\log_2 n)$
#10	$\log_2 n$	$O(\log_2 n)$
#11	1	$O(1)$

この表から、２分探索の計算量は $O(\log_2 n)$ となります。２分探索は、探索リストが大きくなっても線形探索に比べて少ない計算量で探索することが可能であることがわかります。

線形探索

２分探索

Discussion