漸近記法ドリル

目的

第4章「漸近記法」を定着させるための追加問題です。結論だけでなく、反復回数、総和、再帰式、または定義からの証明を書いてください。

難易度ラベル

• [A] 基本: 定義を読む・単純計算をする。
• [B] 標準: 複数の定義を組み合わせる。
• [C] 発展: 証明・設計・実装の説明が必要。
• [D] 実装: 実行可能なコードまたは明確な擬似コードが必要。
• [E] 接続: 本体教科書の概念へ橋渡しする。

A. 定義から示す

1. [A][漸近記法] 3n+7 = O(n) を定義から示せ。
2. [A][漸近記法] n^2+100n+1 = O(n^2) を定義から示せ。
3. [A][漸近記法] 10n^3+n = Θ(n^3) を示せ。
4. [A][漸近記法] n = O(n log n) を n≥2 で説明せよ。
5. [A][漸近記法] log n = O(n) を説明せよ。
6. [A][漸近記法] n^2 は O(n) ではないことを示せ。
7. [A][漸近記法] 2n^2+3n = Ω(n^2) を示せ。
8. [A][漸近記法] n log n = Ω(n) を n≥2 で説明せよ。

B. 増加率を比較する

1. [B][漸近記法] n, log n, n^2, n log n, 2^n, 1 を小さい順に並べよ。
2. [B][漸近記法] n^3, n!, 2^n, n^2 log n, log^2 n を小さい順に並べよ。
3. [B][漸近記法] 1000000n と 0.001n^2 は、漸近的にはどちらが大きいか。
4. [B][漸近記法] n^10 と 2^n は、漸近的にはどちらが大きいか。

C. ループ解析

1. [B][漸近記法] 次の計算量を求めよ。

for i = 1 to n:
    constant_work()

1. [B][漸近記法] 次の計算量を求めよ。

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

1. [B][漸近記法] 次の計算量を求めよ。

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

1. [B][漸近記法] 次の計算量を求めよ。

for i = 1 to n:
    j = 1
    while j < n:
        j = 2 * j

1. [C][漸近記法] 次の計算量を求めよ。

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

1. [C][漸近記法] 次の計算量を求めよ。

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

D. 再帰式

1. [C][漸近記法] T(n)=T(n/2)+1 の解を求めよ。
2. [C][漸近記法] T(n)=2T(n/2)+n の解を求めよ。
3. [C][漸近記法] T(n)=T(n-1)+1 の解を求めよ。
4. [C][漸近記法] T(n)=T(n-1)+n の解を求めよ。
5. [C][漸近記法] T(n)=2T(n-1)+1 は多項式時間か。理由を述べよ。

代表解

• 13: Θ(n)。
• 14: Θ(n^2)。
• 15: Θ(n^2)。総反復回数は n(n+1)/2。
• 16: 外側 n 回、内側 Θ(log n) 回なので Θ(n log n)。
• 17: Θ(log n)。
• 18: Θ(n^3)。
• 19: Θ(log n)。
• 20: Θ(n log n)。
• 21: Θ(n)。
• 22: Θ(n^2)。
• 23: 指数的。各段で呼び出しが2倍になるため、多項式時間ではない。