# 練習問題

## 知識の確認

### 反復と再帰の時間と空間

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

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

<!-- numbered-subquestions -->

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$ を入力します。時間計算量が小さい順に並べ、それぞれの計算量を書いてください。

```src
[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` の全要素を反転する方法として、次の二つがあります。

<!-- numbered-subquestions -->

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](https://leetcode.com/problems/fibonacci-number/){ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }