mirror of
https://github.com/krahets/hello-algo.git
synced 2026-10-30 12:16:13 +08:00
7257641e0e
* Retranslate the complete Japanese online edition from Chinese * Fit Japanese homepage labels and localize heading permalinks * Point Japanese contribution instructions to the Japanese preview * Replace locale conditionals with multilingual UI tables
88 lines
4.7 KiB
Markdown
88 lines
4.7 KiB
Markdown
# 練習問題
|
||
|
||
## 知識の確認
|
||
|
||
### 反復と再帰の時間と空間
|
||
|
||
次の二つのコードは、どちらも $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" }
|