hello-algo/ja/docs/chapter_computational_complexity/exercises.md

練習問題

知識の確認

反復と再帰の時間と空間

次の二つのコードは、どちらも $1 + 2 + \dots + n$（n \ge 1 とします）を計算します。n を 4 に設定し、 プログラムが実際に実行される順に沿って問いに答え、二つの書き方の効率を比較してください。

[file]{complexity_exercises}-[class]{}-[func]{sum_iter}

1. n = 4 を入力して反復関数を実行すると、各反復の終了後に累積変数 res の値はそれぞれいくつになりますか。
2. n = 4 を入力して再帰関数を実行すると、引数 n は順にどの値を取りますか。最も深い呼び出しから戻るとき、結果はどのように求まりますか。
3. 二つの書き方の時間計算量と空間計算量はそれぞれいくつですか。問い 1、2 の実行過程に基づいて理由を説明してください。

??? success "解答例"

1. ループ変数 `i` は順に `1、2、3、4` となり、各反復の終了後に `res` は
    `1、3、6、10` となります。したがって、反復関数は 10 を返します。

2. 引数 `n` は順に `4 → 3 → 2 → 1` となります。
    最も深い呼び出しが 1 を返し、その後、各呼び出しで順に `2 + 1 = 3`、`3 + 3 = 6`、`4 + 6 = 10` が求まります。
    最も深い位置では、4 回の関数呼び出しがすべて未完了です。

3. どちらも $n$ に比例する回数のループまたは呼び出しを行うため、時間計算量はともに $O(n)$ です。
    空間計算量は異なります。反復版は定数個の変数だけを使うので、$O(1)$ です。
    再帰版では、終了条件に達するまで、先に行った関数呼び出しが結果を待ち続けます。このため、呼び出しスタックには最大で $n$ 回の呼び出しが同時に保持され、
    空間計算量は $O(n)$ となります。

    空間計算量の解析では、コード中の変数に加え、再帰呼び出しが使う領域も考慮する必要があります。

三つのコードの時間計算量

次の三つのコード片には、いずれも正の整数 n を入力します。時間計算量が小さい順に並べ、それぞれの計算量を書いてください。

[file]{complexity_exercises}-[class]{}-[func]{linear_loop}

??? success "解答例"

小さい順に、コード片 3 が $O(\log n)$、コード片 1 が $O(n)$、コード片 2 が $O(n^2)$ です。
コード片 3 は、各反復で $n$ を半分にするため、約 $\log_2 n$ 回繰り返します。
コード片 1 のループは、ちょうど $n$ 回実行されます。コード片 2 の内側のループ回数は順に
$n,n-1,\dots,1$ で、合計 $n(n+1)/2$ 回となるため、二次のオーダーです。

領域を節約できる反転方法

配列 nums の全要素を反転する方法として、次の二つがあります。

1. 同じ長さの配列 res を新しく作り、逆順にコピーして返します。

2. 二つのインデックス i と j をそれぞれ先頭と末尾から中央へ進め、nums[i] と nums[j] を一組ずつ交換します。

   それぞれの空間計算量はいくつですか。どちらが「インプレース」の操作ですか。

??? success "解答例"

1. 入力と同じ長さの補助配列が必要なので、空間計算量は $O(n)$ です。

2. 二つのインデックス変数だけを使うため、
    空間計算量は $O(1)$ で、インプレースの操作です。

    注意点として、インプレースの反転は入力配列を変更します。
    入力の変更が許される場合に限って優先すべきです。元の配列を残す必要があれば、方法 1 のコピーにかかるコストは避けられません。

プログラミング演習

フィボナッチ数

フィボナッチ数列は、$F(0)=0$、F(1)=1 を満たし、n\ge2 のとき F(n)=F(n-1)+F(n-2) が成り立ちます。

非負整数 n が与えられます。再帰を使わず、ループで F(n) を計算して返してください。

??? tip "解くためのヒント"

1. まず n が 0 と 1 の場合を個別に処理します
2. 次の項の計算には直前の二項だけが必要で、数列全体を保持する必要はありません
3. 二つの変数を更新するときは、まだ使う古い値を先に上書きしないように注意します

LeetCode{ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }