Pythonプログラミングイントロダクション10章まで読みました。
9,10章は計算複雑性についてです。O(n)となる線形な計算量はイメージしやすいのですが、O(log n) のように対数が出てくるケースがどういうケースか最初イメージしずらかった覚えがあります。
この本では、9章で計算複雑性についての概念を、10章では二分探索やマージソートを例に、計算複雑性に対数が現れる様子を詳しく説明してくれています。
計算複雑性
9章で下記の計算複雑性について説明されています。
| O(1) | 定数計算時間 | |
|---|
| O(log n) | 対数計算時間 | |
| O(n) | 線形計算時間 | |
| O(n log n) | 対数線形計算時間 | |
| O(n^k) | 多項式計算時間 | k:定数 |
| O(c^n) | 指数計算時間 | c:定数 |
前述したように定数計算時間や線形計算時間はイメージしやすいです。定数計算時間なら入力によらず計算時間は一定となり、線形計算時間なら入力に比例して計算時間が増加します。
計算複雑性に対数が現れるケース
本書では O(log n): 対数計算時間や、O(n log n):線形対数計算時間となる場合を二分探索とマージソートを例に説明してくれています。
対数計算時間と二分探索
下記は二分探索のコード例です。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| 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)となります。こうやって対数が計算複雑性に現れます。
線形対数計算時間とマージソート
下記はマージソートのコード例です。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| 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章で詳しく取り扱うとのこと。読み進める楽しみができました。
