アルゴリズムの計算量
定数・線形・二乗・対数の増え方を具体的な操作数から学びます。
説明
計算量は入力が大きくなったときに必要な処理や領域がどう増えるかを表します。秒数は機器や実装で変わるため、まず何を1回と数えるか決めます。ここでは配列参照、要素の処理、組の処理、半減の回数をそれぞれ数えます。
入力数を4・8・16と増やし、一回の参照、全要素の走査、全組合せの二重ループ、半分ずつ縮める処理を比較します。最後に式の支配項と、O記法から分からないことを整理します。
1添字で一つ参照
配列から一つの添字を指定する操作を、入力数ごとに行います。配列を作る処理はここで数える参照の費用に含めません。
sizes = [4, 8, 16]比較する入力数; [(n, list(range(n))[n//2], 1) for n in sizes]中央の1要素を参照各組は入力数・参照した値・参照回数です。どの大きさでも一つの添字を参照する回数は1です。固定幅の添字や参照を一定費用とするモデルで、これを定数時間と考えます。
2全要素を一回ずつ処理
range(n)の各要素に対して1を加算し、何個処理したか数えます。
linear_counts = [(n, sum(1 for _ in range(n))) for n in sizes]各要素の処理回数; linear_counts入力数と回数4・8・16回で、入力数を2倍にすると処理回数も2倍です。この増え方を線形と呼びます。ループ内で行う処理が一定費用という条件も含みます。
3全ての順序付きの組を処理
外側も内側もn回動く二重ループです。同じ添字同士も含め、(i,j)の全ての組を処理します。
square_counts = [(n, sum(1 for i in range(n) for j in range(n))) for n in sizes]二重ループを数える; square_counts入力数と全組数16・64・256回となり、入力数2倍で4倍です。内側をn回実行する処理が外側のn回分あるため、積n²になります。
4内側の範囲が短い二重ループ
同じ組を逆順で重複処理しないよう、i<jだけを数えます。二重ループという形だけでなく、各回の範囲を調べます。
pairs = [(n, sum(1 for i in range(n) for j in range(i+1, n))) for n in sizes]重複しないペアを数える; pairs入力数とペア数6・28・120回です。式はn(n-1)/2で、全順序付きのn²より少なくなります。それでも大きなnで中心になる項はn²なので、二乗の増加として扱います。
5半分ずつ縮める
大きさが1になるまで整数除算で半分にします。途中の大きさを履歴に残します。
def halve(n):初期サイズ
trace = [n]最初の大きさ
while n > 1:1になるまで
n //= 2半分にする
trace.append(n)途中値を記録
return trace全段階を返す2のべき乗を使うと4→2→1のように正確に半減します。入力を2倍にしても追加される段階は一つだけです。
6入力を半分にできる回数
4・8・16に加えて1024でも計算します。履歴の最初を除いた個数が半減の回数です。
[(n, halve(n), len(halve(n))-1) for n in [4, 8, 16, 1024]]入力・縮小履歴・回数半減回数は2・3・4・10です。2を何回掛ければ入力数になるかというlog₂nと対応します。対数の底が違っても一定倍率の差なので、O記法では通常O(log n)と書きます。
7支配項の割合
処理回数が3n²+10n+20という式だった場合、n²の項が全体のどれだけを占めるか調べます。
[(n, 3*n*n+10*n+20, round((3*n*n)/(3*n*n+10*n+20), 4)) for n in [10, 100, 1000]]総回数と二乗項の割合nが増えるほど二乗項の割合が1へ近づきます。定数倍率や低次の項を省いてO(n²)と表すのは、この増え方の上界に注目するためです。Oは厳密な等号や秒数を表す記号ではありません。
8小さい入力では定数も効く
100nとn²を比較します。線形の式の方が常に小さいとは限りません。
[(n, 100*n, n*n, 100*n < n*n) for n in [10, 100, 1000]]定数の大きい線形と二乗を比較n=10では二乗の100が線形の1000より小さく、n=100で等しく、n=1000では線形の方が小さくなります。計算量は入力の増加に対する指標で、特定サイズの実行速度を決めるには定数や実装も必要です。
まとめ
何を1回と数えるかを固定して、入力数に対する増え方を調べます。
全走査は線形、全ペアは二乗、半減の反復は対数という増え方になります。
O記法は漸近的な上界です。秒数や小さい入力での優劣をそのまま示すものではありません。
操作履歴と解説を振り返れます。
Python 3
sizes = [4, 8, 16]; [(n, list(range(n))[n//2], 1) for n in sizes][(4, 2, 1), (8, 4, 1), (16, 8, 1)]
linear_counts = [(n, sum(1 for _ in range(n))) for n in sizes]; linear_counts[(4, 4), (8, 8), (16, 16)]
square_counts = [(n, sum(1 for i in range(n) for j in range(n))) for n in sizes]; square_counts[(4, 16), (8, 64), (16, 256)]
pairs = [(n, sum(1 for i in range(n) for j in range(i+1, n))) for n in sizes]; pairs[(4, 6), (8, 28), (16, 120)]
def halve(n):
trace = [n]
while n > 1:
n //= 2
trace.append(n)
return trace[(n, halve(n), len(halve(n))-1) for n in [4, 8, 16, 1024]][(4, [4, 2, 1], 2), (8, [8, 4, 2, 1], 3), (16, [16, 8, 4, 2, 1], 4), (1024, [1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1], 10)]
[(n, 3*n*n+10*n+20, round((3*n*n)/(3*n*n+10*n+20), 4)) for n in [10, 100, 1000]][(10, 420, 0.7143), (100, 31020, 0.9671), (1000, 3010020, 0.9967)]
[(n, 100*n, n*n, 100*n < n*n) for n in [10, 100, 1000]][(10, 1000, 100, False), (100, 10000, 10000, False), (1000, 100000, 1000000, True)]
演習完了