リリース・改善中
Algorithm
O記法を使って、アルゴリズムの実行時間とメモリが入力サイズに応じてどう増えるかを解析し、実測で確かめる方法を学びます。
計算量解析は、入力が大きくなったときにアルゴリズムが必要とする時間とメモリがどれだけ増えるかを表す方法です。ハードウェアや言語で変わる秒数ではなく、基本操作の回数を入力サイズ n の関数として数え、最も大きい項だけを残します。結果は漸近記法で書き、上界には O(ビッグオー)、下界には Ω(ビッグオメガ)、ぴったりの次数には Θ(ビッグシータ)を使います。
データが大きくなると、オーダーの差はどんな定数倍の差よりも大きくなるため、計算量解析が重要になります。要素数千個では問題のなかった O(n²) のコードが、百万個では何時間もかかることがありますが、O(n log n) のコードなら数秒で終わります。データ構造の選択、競技プログラミングやコーディング面接での入力制約の読み取り、コードレビューでの隠れたコストの発見、システムが拡張に耐えられるかの見積もりに、計算量の考え方を使います。
まず簡単なループの操作回数を数え、O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ)、O(n!) といった代表的なオーダーを身につけます。次に最良・平均・最悪の場合、償却解析、空間計算量、マスター定理による漸化式の解き方へ進みます。学習中は、n と 2n で時間を測って比を比べる倍増実験で、解析が正しいかを確かめる習慣をつけると効果的です。
O、Ω、Θ は定数倍や低次の項を無視して、増え方の上界、下界、ぴったりの次数を表します。
順に並んだ処理はコストを足し、入れ子のループは掛け、毎回問題を半分にするなら対数になります。
一連の操作全体の総コストを操作数で割って保証します。動的配列への追加がときどき全体をコピーしても O(1) とされる理由です。
補助メモリと再帰の深さもコストに含まれ、分割統治の漸化式はマスター定理で解けます。
同じ問題を、すべてのペアを調べる方法と、見た値を辞書に記録しながら一度だけ走査する方法で解きます。n = 500、1,000、2,000 で timeit を使って両方を測ると、n が 2 倍になるたびに二乗の版は約 4 倍、線形の版は約 2 倍遅くなります。
complexity.py
import timeit
def two_sum_quadratic(nums, target):
"""O(n^2): try every pair."""
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return i, j
return None
def two_sum_linear(nums, target):
"""O(n) on average: remember values already seen."""
seen = {}
for j, x in enumerate(nums):
i = seen.get(target - x)
if i is not None:
return i, j
seen.setdefault(x, j)
return None
print(two_sum_quadratic([8, 3, 11, 5, 2], 13), two_sum_linear([8, 3, 11, 5, 2], 13))
for n in (500, 1_000, 2_000):
nums = list(range(0, 2 * n, 2)) # even numbers only, so no pair sums to -1
slow = timeit.timeit(lambda: two_sum_quadratic(nums, -1), number=3) / 3
fast = timeit.timeit(lambda: two_sum_linear(nums, -1), number=3) / 3
print(f"n={n:>5} O(n^2) {slow * 1000:8.2f} ms O(n) {fast * 1000:6.3f} ms")
python complexity.pyインストールから 計算量解析 の中心となる考え方まで、6 章で順を追って学びます。
計算量解析 について質問し、経験を共有し、意見を交わす場所です。
まだディスカッションはありません。最初の話題を始めましょう。
コメント 0件
ログイン · ログインするとコメントできます。
最初のコメントを書いてみましょう。