Pythonプログラミングイントロダクション(9-10章) 計算複雑性の対数はどこからくるのか?

2019–11–25

9,10章は計算複雑性についてです。O(n)となる線形な計算量はイメージしやすいのですが、O(log n) のように対数が出てくるケースがどういうケースか最初イメージしずらかった覚えがあります。 この本では、9章で計算複雑性についての概念を、10章では二分探索やマージソートを例に、計算複雑性に対数が現れる様子を詳しく説明してくれています。

計算複雑性

9章で下記の計算複雑性について説明されています。

O(1) 定数計算時間
O(log n) 対数計算時間
O(n) 線形計算時間
O(n log n) 対数線形計算時間
O(nk) 多項式計算時間 k:定数
O(cn) 指数計算時間 c:定数

前述したように定数計算時間や線形計算時間はイメージしやすいです。定数計算時間なら入力によらず計算時間は一定となり、線形計算時間なら入力に比例して計算時間が増加します。

計算複雑性に対数が現れるケース

本書では O(log n): 対数計算時間や、O(n log n):線形対数計算時間となる場合を二分探索とマージソートを例に説明してくれています。

対数計算時間と二分探索

下記は二分探索のコード例です。

def binary_search(lis, val):
    u""" 引数で与えられたListの中から検索valの位置を検索して返す。
    検索値が存在しない場合は-1を返す
    """

    length = len(lis)
    if length == 0:
        return -1

    return _search_array(lis, val,  0, length - 1)

def _search_array(lis, val, start, end):

    mid = int((start + end) / 2)
    if start == end  and lis[mid] != val:
        return -1

    if lis[mid] == val:
        return mid

    elif lis[mid] > val:
        if (start == mid):
            return -1
        return _search_array(lis, val, start, mid - 1)

    else:
        return _search_array(lis, val, mid + 1, end)

    return -1

print(binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], 1))
print(binary_search([1, 3, 5, 8], 4))	  
: 0
: -1	  

_search_binaryメソッドは与えられたリストを元に、検索する値が存在しない場合はリストの長さが1になるまで、リストの長さを半分にしながら再帰し続けます。 つまり、再帰回数をxとしたときに、

\[ 2^x = リストの長さ \]

\[ x = \log_{2} (リストの長さ) \]

\[ リストの長さを n とすると \]

\[ x = \log_{2} n \]

つまり計算複雑性は O(log n)となります。こうやって対数が計算複雑性に現れます。

線形対数計算時間とマージソート

下記はマージソートのコード例です。

def merge_sort(lis):
    return split_list(lis)

def split_list(arr):
    """
    リストを半分に分ける
    リストの要素が2つになったところで比較を行い、比較した結果をmerge_arrメソッドに渡す。
    """
    if len(arr) <= 1:
        return arr
    elif len(arr) == 2:
        if arr[0] > arr[1]:
            return [arr[1], arr[0]]
        else:
            return arr

    else:
        br = int(len(arr) / 2)
        return merge_arr(split_list(arr[:br]), split_list(arr[br:]))

def merge_arr(arr1, arr2):
    """
    ソート済みの渡されたリストを相互に比較しながらマージする。
    """

    ret = list()
    len1 = len(arr1)
    len2 = len(arr2)

    i = j = 0
    arr1_val = arr1[i]
    arr2_val = arr2[j]

    while len(ret) < len1 + len2:

        if arr1_val < arr2_val:
            ret.append(arr1_val)
            if i < len1 - 1:
                i += 1
                arr1_val = arr1[i]
            else:
                arr1_val = float('inf')

        elif arr1_val >= arr2_val:
            ret.append(arr2_val)
            if j < len2 - 1:
                j += 1
                arr2_val = arr2[j]
            else:
                arr2_val = float('inf')

    return ret

print(merge_sort([]))
print(merge_sort([1]))
print(merge_sort([1, 10, 2, 3, 5, 4, 0]))	  
: []
: [1]
: [0, 1, 2, 3, 4, 5, 10]	  

split_listメソッドは与えられたリストの長さを元にすると、リストの長さが2以下になるまで再帰し続けます。これは二分探索と同じ計算時間になりますので、O(log n)になります。 merge_arrメソッドでは、while文でリストの長さ分ループしながら比較して要素の位置を更新していますので、計算時間は O(n)になります。 よって、これら二つを掛け合わせたものが計算時間になるので、O(n lon n)となります。

まとめ

9,10章から対数が現れる計算複雑性について取り上げました。対数が現れる計算複雑性のケースを有名なアルゴリズムとセットで学ぶことができました。 10章ではハッシュデータ構造についても言及があり、チェーン法のような実装が提示されていますが、15章で詳しく取り扱うとのこと。読み進める楽しみができました。