第4章 漸近記法

章間ナビゲーション

• 前: 第3章 証明技法
• 次: 第5章 擬似コードと再帰
• 章別マップ: 章間リンクマップ
• 用語確認: 用語索引 / 記号索引
• 到達判定: 章末確認チェック

この章で使う記号

この章で解消する詰まりどころ

アルゴリズム解析では、実行時間を秒数ではなく、入力サイズ n に対する増え方で評価します。この増え方を表す記法が漸近記法です。

この章の目的は、次の状態を作ることです。

• O, Ω, Θ の違いを定義で説明できる。
• 簡単な関数について、定義から O を証明できる。
• ループ、ネストしたループ、対数時間ループの計算量を評価できる。
• 再帰式を見て、何を意味しているか説明できる。
• 「速い」「遅い」を定数時間ではなく増加率で判断できる。

本体教科書のどこで使うか

• 第5章 計算複雑性理論
• 第6章 アルゴリズムの数学的解析
• 第7章 データ構造の理論
• 第8章 グラフ理論とネットワーク
• 第11章 暗号理論での計算困難性

1. 入力サイズ

計算量は、入力そのものではなく、入力サイズに対して評価します。

例:

注意点として、整数問題では、入力サイズは整数 N そのものではなく、通常は表現に必要なビット数 ⌈log2(N+1)⌉ です。

2. 時間計算量と空間計算量

時間計算量は、入力サイズが増えたとき、必要な基本操作回数がどう増えるかを表します。

空間計算量は、入力以外に必要なメモリ量がどう増えるかを表します。

例:

for i = 1 to n:
    print(i)

このコードは n 回反復するので、時間計算量は Θ(n) です。追加メモリが定数個の変数だけなら、空間計算量は Θ(1) です。

3. O記法

f(n) = O(g(n)) とは、十分大きな n について、f(n) が定数倍の g(n) 以下で抑えられるという意味です。

定義:

f(n) = O(g(n))
⇔ ある正定数 c と n0 が存在して、すべての n ≥ n0 について
   0 ≤ f(n) ≤ c g(n)

直観:

g(n) は f(n) の漸近的な上界である。

例：5n^2 + 20n + 1 = O(n^2)

示すこと:

ある c,n0 が存在して、n≥n0 なら 5n^2+20n+1 ≤ c n^2

n≥1 なら、20n ≤ 20n^2 かつ 1 ≤ n^2 です。したがって、

5n^2 + 20n + 1 ≤ 5n^2 + 20n^2 + n^2 = 26n^2

よって c=26, n0=1 とすればよいです。

4. Ω記法

f(n) = Ω(g(n)) とは、十分大きな n について、f(n) が定数倍の g(n) 以上であるという意味です。

定義:

f(n) = Ω(g(n))
⇔ ある正定数 c と n0 が存在して、すべての n ≥ n0 について
   0 ≤ c g(n) ≤ f(n)

直観:

g(n) は f(n) の漸近的な下界である。

例:

5n^2 + 20n + 1 = Ω(n^2)

n≥1 なら 5n^2 ≤ 5n^2 + 20n + 1 なので、c=5, n0=1 とできます。

5. Θ記法

f(n) = Θ(g(n)) とは、f(n) と g(n) が定数倍を除いて同じ増加率であるという意味です。

定義:

f(n) = Θ(g(n))
⇔ f(n) = O(g(n)) かつ f(n) = Ω(g(n))

例:

5n^2 + 20n + 1 = Θ(n^2)

上で O(n^2) と Ω(n^2) の両方を示したので、Θ(n^2) です。

6. よく使う成長率

典型的な大小関係は次です。

1 < log n < n < n log n < n^2 < n^3 < 2^n < n!

十分大きな n では、指数関数は任意の多項式より速く増えます。

代表例

7. 支配項と定数の無視

漸近記法では、十分大きな n における増え方だけを見ます。そのため、定数倍と低次項は無視されます。

例:

100n + 1000000 = Θ(n)
0.001n^2 + n = Θ(n^2)
5n log n + 20n = Θ(n log n)

ただし、実務上の実行時間では定数倍が効くことがあります。漸近記法は大規模入力での増加率を見る道具であり、常に実測性能を完全に予測するものではありません。

8. 定義から証明する手順

f(n)=O(g(n)) を示すには、次の形を作ります。

f(n) ≤ c g(n)

手順:

1. 十分大きい n を仮定する。たとえば n≥1。
2. 低次項を高次項で上から抑える。
3. 定数をまとめる。
4. c と n0 を明示する。

例：n^2 = O(n^3)

n≥1 なら n^2 ≤ n^3 です。したがって、c=1, n0=1 とすれば、すべての n≥1 で n^2 ≤ c n^3 です。よって n^2=O(n^3) です。

反例：n^3 は O(n^2) ではない

仮に n^3 = O(n^2) だとすると、ある c,n0 が存在して、すべての n≥n0 で

n^3 ≤ c n^2

が成り立つはずです。n^2 > 0 で割ると、

n ≤ c

となります。しかし、n はいくらでも大きく取れるので、固定された定数 c で常に n≤c とすることはできません。矛盾です。したがって n^3 は O(n^2) ではありません。

9. 単純なループ

for i = 1 to n:
    constant_work()

反復回数は n 回です。各反復が Θ(1) なら、全体は Θ(n) です。

for i = 1 to n:
    for j = 1 to n:
        constant_work()

外側が n 回、内側が各回 n 回なので、全体は n^2 回です。計算量は Θ(n^2) です。

10. 三角形型の二重ループ

for i = 1 to n:
    for j = 1 to i:
        constant_work()

反復回数は、

1 + 2 + ... + n = n(n+1)/2

です。したがって計算量は Θ(n^2) です。

同様に、

for i = 1 to n:
    for j = i to n:
        constant_work()

の反復回数も、

n + (n-1) + ... + 1 = n(n+1)/2

なので Θ(n^2) です。

11. 対数時間ループ

i = n
while i > 1:
    i = floor(i / 2)

i は各反復で半分になります。k 回後には、おおよそ n/2^k です。

ループが止まるのは、

n / 2^k ≤ 1

となるときです。これは、

2^k ≥ n

つまり、

k ≥ log2 n

です。したがって計算量は Θ(log n) です。

倍々で増えるループ

i = 1
while i < n:
    i = 2 * i

こちらも i が倍々で増えるため、反復回数は Θ(log n) です。

12. 再帰式の入口

再帰的アルゴリズムの計算量は、再帰式で表すことがあります。

例：二分探索

二分探索は、配列を半分に絞ります。

T(n) = T(n/2) + Θ(1)

これは、

• 半分サイズの問題を1つ解く。
• それ以外の比較などに定数時間を使う。

という意味です。解は T(n)=Θ(log n) です。

例：マージソート

マージソートは、配列を半分ずつ2つに分け、最後に線形時間でマージします。

T(n) = 2T(n/2) + Θ(n)

解は T(n)=Θ(n log n) です。

例：単純なフィボナッチ再帰

fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

概略として、再帰呼び出しが木状に増えるため、指数時間になります。正確な評価は不要ですが、少なくとも多項式時間ではありません。

13. 計算量解析の書き方

計算量を答えるときは、結論だけでなく根拠を付けます。

悪い例:

O(n^2) です。

良い例:

外側ループは n 回実行される。内側ループは各 i に対して i 回実行される。
したがって総反復回数は 1+2+...+n = n(n+1)/2 である。
各反復の処理が定数時間なので、時間計算量は Θ(n^2) である。

O だけでは上界しか述べていません。正確な増加率が分かる場合は Θ を使います。

14. よくある誤り

誤り1：O記法を実行時間そのものだと思う

O(n) は秒数ではありません。入力サイズに対する増加率の上界です。

誤り2：常に最悪計算量を見ていることを忘れる

計算量には、最悪、平均、最良があります。明示されていなければ、通常は最悪計算量を考えます。

誤り3：O と Θ を混同する

n = O(n^2) は真です。しかし、n = Θ(n^2) は偽です。O は上界、Θ は同程度です。

誤り4：入力サイズを間違える

整数 N の入力サイズを N として扱うと、数論アルゴリズムの評価で誤ります。通常はビット長 log N です。

15. 練習問題

1. 7n+3 = O(n) を定義から示せ。
2. 4n^3 + n^2 + 100 = Θ(n^3) を示せ。
3. n log n = O(n^2) を説明せよ。
4. 2^n が O(n^k) ではないことを直観的に説明せよ。ただし k は固定された正整数。
5. 次の計算量を求めよ。

for i = 1 to n:
    for j = 1 to n:
        for k = 1 to 10:
            constant_work()

1. 次の計算量を求めよ。

i = 1
while i < n:
    i = 3 * i

1. T(n)=T(n/2)+Θ(1) が Θ(log n) になる理由を説明せよ。
2. T(n)=2T(n/2)+Θ(n) が Θ(n log n) になる直観を説明せよ。

次に読む章

• 通常ルート: 第5章 擬似コードと再帰
• 演習: Core 演習
• 解答: 演習解答
• 図表: 関連図表
• 実装確認: Python実装ノート
• 全体導線: 学習チェックリスト