企业官网建设流程全解析

《Hello 算法》計算量解析の章末演習を徹底解説：反復と再帰・O記法の考え方を実例で身につける

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

「反復と再帰、どちらの書き方が効率的か」「3 つのコードの時間計算量をどう見抜くか」「インプレース操作が本当に空間を節約するのか」——こうした問いはアルゴリズム設計の土台となる判断力そのものです。本記事は日本語版ドキュメントの 計算量解析・章末演習 を題材に、章の本文（反復と再帰、時間計算量、空間計算量）と対応するソースコードを照合しながら、各問題の考え方・正答・コード上の根拠を順に解説します。読み終える頃には、実装を見て時間・空間計算量を手早く見積もり、状況に応じて反復と再帰、コピーとインプレースを適切に選べるようになります。

演習が想定する前提知識：この章で身につける「複雑度の見方」

演習を解く前に、計算量解析の土台となる考え方を確認しておきましょう。章の冒頭で述べられている通り、アルゴリズム効率を測る指標は時間効率と空間効率の 2 つであり、実測に頼らず数式で評価するのが「計算量解析」です（章のまとめ）。

• 時間計算量：操作回数 $T(n)$ が入力サイズ $n$ に対してどのような漸近上界を持つかで表します。ビッグオー記法 $O$ を用い、$n$ が大きくなるにつれて実行時間がどう増えるかを記述します（時間計算量の章）。
• 空間計算量：アルゴリズムが使うメモリ量の増加傾向です。入力空間・一時空間・出力空間のうち、通常は入力空間を除いて数えます。特に再帰の場合はスタックフレーム領域が空間計算量に影響する点が本章の重要な注意ポイントです（空間計算量の章）。

複雑度を低い順に並べると $O(1)$、$O(\log n)$、$O(n)$、$O(n \log n)$、$O(n^2)$、$O(2^n)$、$O(n!)$ となり、演習問題はこのうち$O(1)$、$O(\log n)$、$O(n)$、$O(n^2)$ の識別力を鍛える内容になっています。

なお、本章の演習コードは多言語版として一元管理されており、たとえば Python 版は complexity_exercises.py、C++ 版は complexity_exercises.cpp に置かれています。ファイル末尾にはassertによる自動検証（自己テスト）が同梱されているため、実行して正答を確認できます。

確認問題 1：反復と再帰の時間・空間計算量を比較する

$1 + 2 + \dots + n$（ただし $n \ge 1$）を計算する 2 つの関数を、実際にn = 4で実行したときの挙動を追いかけながら比較します。対応する実装は complexity_exercises.py にあります。

def sum_iter(n: int) -> int: """反復による総和""" res = 0 for i in range(1, n + 1): res += i return res def sum_recur(n: int) -> int: """再帰による総和""" if n == 1: return 1 return n + sum_recur(n - 1)

(1) 反復関数：各ループ終了時のres

n = 4のとき、ループ変数iは1 → 2 → 3 → 4の順に変化します。Python のrange(1, n + 1)は左閉右開（$a$ 以上 $b$ 未満）であるため、range(1, 5)はちょうど1, 2, 3, 4を走査します（この点は iteration.py のfor_loopと同じ設計です）。累積変数resは各ループ終了時に次のように更新されます。

したがってsum_iter(4)は10を返します。ソースコード末尾の自己テストにもassert sum_iter(4) == sum_recur(4) == 10という形で検証が組み込まれており、実行すれば正しさを機械的に確かめられます（complexity_exercises.py）。

(2) 再帰関数：引数nの変化と復帰の仕組み

再帰版では、呼び出しのたびに引数が 1 ずつ減っていきます。sum_recur(4)を呼んだ場合の引数の流れは4 → 3 → 2 → 1です。

再帰は「再帰呼び出し」と「復帰」の 2 段階からなります（反復と再帰の章）。

1. 再帰呼び出しの過程：sum_recur(4)は4 + sum_recur(3)を計算するため、まずsum_recur(3)を呼び出します。同様に3 + sum_recur(2)、2 + sum_recur(1)と呼び出しが進みます。この時点ではどの関数もまだ値を返しておらず、4 回分の関数呼び出しがすべて「待機」状態です。
2. 終了条件の発動：n == 1に達すると1を返します（基本ケース）。
3. 復帰の過程：呼び出しの逆順に結果が積み上げられ、2 + 1 = 3→3 + 3 = 6→4 + 6 = 10と求められます。

再帰の正しさは「問題を部分問題に分解する」ことに由来します。$f(n) = 1 + 2 + \dots + n$ を $f(n) = n + f(n-1)$ という部分問題へ分解し、基本ケース $f(1) = 1$ で停止する、というのがこのコードの本質です（反復と再帰の章の「トップダウン」の説明を参照）。

(3) 時間計算量と空間計算量の比較

両者の計算量は以下のようにまとめられます。

時間計算量はどちらも $n$ に比例する回数のループ/呼び出しを行うため$O(n)$ で一致します。一方、空間計算量は大きく異なります。

• 反復版が使う変数はresとiなど定数個であるため $O(1)$ です。
• 再帰版は終了条件に達するまで、それ以前の関数呼び出しがすべて結果を待つ必要があります。システムは呼び出しごとに局所変数・呼び出し先アドレスなどを「スタックフレーム領域」に保存するため、最も深い時点で $n$ 回分のフレームが同時に存在し、空間計算量は $O(n)$ になります（反復と再帰の章）。

この問題の最大の学びは、「空間計算量を分析するときはコード中の変数だけでなく、再帰呼び出しが占める空間も考慮する」という点です。再帰はコードを簡潔にしますが、関数呼び出しのオーバーヘッド（時間）とスタックフレーム（空間）というコストを伴うため、単純な総和のような問題では反復のほうが空間効率に優れます。これは章末の比較表「反復は通常、固定サイズのメモリを使う / 再帰はスタックフレーム領域を大量に使う可能性がある」とも整合します。

確認問題 2：3 つのコード片の時間計算量を小さい順に並べる

3 つのコード片はどれも正の整数 $n$ を入力とします。実体は complexity_exercises.py の 3 関数に対応しています。

# コード片 1：線形時間のループ def linear_loop(n: int) -> int: res = 0 for i in range(n): res += i return res # コード片 2：二次時間のループ def quadratic_loop(n: int) -> int: res = 0 for i in range(n): for j in range(i, n): res += j return res # コード片 3：対数時間のループ def logarithmic_loop(n: int) -> int: while n > 1: n //= 2 return n

正答：$O(\log n)$ < $O(n)$ < $O(n^2)$

時間計算量が小さい順に並べると次の通りです。

それぞれの導出過程

コード片 3（$O(\log n)$）：while n > 1の内部でn //= 2（整数除算で半分にする）を実行します。1 回のループで $n$ が半分になるため、ループ回数はおよそ $\log_2 n$ 回です。たとえば $n = 8$ なら8 → 4 → 2 → 1と 3 回、$n = 16$ なら 4 回で、まさに対数関数的な増加です。「半分ずつ減っていくループ」は、二分探索をはじめ多くのアルゴリズムの基本パターンです。なお、この関数は「何かを計算する」というよりループ回数そのものを題材にしたコード片であり、$n$ を 2 で割り続けた末に 1 を返します。

コード片 1（$O(n)$）：for i in range(n)によりiは0, 1, ..., n-1とちょうど $n$ 回変化し、ループも $n$ 回実行されます。操作回数が $n$ に比例する典型的な線形階です。

コード片 2（$O(n^2)$）：外側のループが $n$ 回回る間に、内側のループfor j in range(i, n)の実行回数は $i$ ごとに

$$ n,\ n-1,\ n-2,\ \dots,\ 1 $$

と減少していきます。総実行回数は等差数列の和となり

$$ n + (n-1) + \dots + 1 = \frac{n(n+1)}{2} $$

です。最高次の項は $n^2/2$ なので、漸近上界を取ると$O(n^2)$（平方階）になります。ビッグオー記法では定数係数（$1/2$）と低次の項（$n/2$）は無視する、というルールを再確認できる良い例です。

このように「ループの構造を見れば時間計算量が推定できる」ことが、この問題の狙いです。$O(1)$、$O(\log n)$、$O(n)$、$O(n \log n)$、$O(n^2)$ などの各階の定義と典型例は 時間計算量の章の「よくある種類」節 に図解つきでまとめられています。自己テスト（linear_loop(4) == 6、quadratic_loop(4) == 20など）は計算量そのものではなく実装の正しさを担保するものですが、コード片の意図を追ううえで役立ちます。

確認問題 3：配列反転——どちらの方法が空間を節約できるか

配列numsの全要素を逆順にする 2 つの方法について、空間計算量と「インプレース」性を考えます。

方法 1：等長の新しい配列に逆順コピー

def reverse_with_copy(nums: list[int]) -> list[int]: """新しい配列を作って逆順にコピー""" n = len(nums) res = [0] * n # 入力と同長の補助配列 for i in range(n): res[i] = nums[n - 1 - i] return res

入力と同じ長さの補助配列resが必要になるため、空間計算量は$O(n)$です。元のnumsは変更されず、新しい配列を返す設計になっています。

方法 2：先頭と末尾から 2 つのインデックスで交換（インプレース）

def reverse_in_place(nums: list[int]) -> None: """2 つのインデックスで逐対交換（インプレース）""" i, j = 0, len(nums) - 1 while i < j: nums[i], nums[j] = nums[j], nums[i] # 逐対交換 i += 1 j -= 1

使用するのはインデックス変数iとjの定数個だけなので、空間計算量は$O(1)$であり、インプレース（in-place）な操作です。配列の反転に「追加の配列」は必要なく、要素の交換だけで完結します。Python ではnums[i], nums[j] = nums[j], nums[i]という同時代入で一時変数なしに交換できます。

どちらを選ぶべきか——トレードオフの視点

演習の解答にある通り、結論は以下の通りです。

• 方法 2（インプレース）は空間効率が良いが、入力配列そのものを変更します。入力の変更が許される場合にのみ優先すべきです。
• 元の配列を残しておく必要がある場合は、方法 1 のコピーにかかる空間 $O(n)$ を省くことはできません。

つまり「空間を節約したいからといって常にインプレースを選べばよい」わけではなく、入力データを破壊してよいかという要件とセットで判断する必要があります。これは「時間と空間のトレードオフ」の考え方（空間計算量の章の「時間と空間のトレードオフ」節）にも通じる視点です。空間計算量は「追加でどれだけメモリを使うか」で評価するため、入力配列そのもののサイズは通常カウントしない点もあわせて覚えておきましょう。

プログラミング演習：フィボナッチ数をループで計算する

章の締めくくりは、再帰を使わずにフィボナッチ数列を計算するプログラミング演習です。フィボナッチ数列は

$$ F(0)=0,\quad F(1)=1,\quad F(n)=F(n-1)+F(n-2)\ (n\ge2) $$

を満たす数列で、非負整数nが与えられたとき、ループだけで $F(n)$ を計算して返すことが求められます（外部オンラインジャッジの「フィボナッチ数」問題に相当する出題です）。

解法のヒントの噛み砕き

演習に付属するヒントは、次の 3 点に要約できます。

1. $n$ が 0 と 1 の場合を先に処理する——これらは基本ケースで、それぞれ $F(0)=0$、$F(1)=1$ をそのまま返せます。
2. 数列全体を保存する必要はない——次の項の計算に必要なのは直前の 2 項だけです。配列で全項を持てば空間 $O(n)$ になりますが、2 変数の更新方式なら空間 $O(1)$ で済みます。
3. 古い値を先に上書きしない——たとえば「現在の項」を先に更新してしまうと、「次の項」の計算に必要な前の値が失われます。更新順序か同時代入に注意します。

解答例（Python）

def fib(n: int) -> int: """フィボナッチ数：ループ（反復）による解法""" if n == 0: return 0 # 基本ケース F(0) = 0 if n == 1: return 1 # 基本ケース F(1) = 1 a, b = 0, 1 # F(0), F(1) for _ in range(2, n + 1): a, b = b, a + b # 同時代入：a = F(i-1), b = F(i) を前進 return b

a, b = b, a + bは「右辺をすべて評価してから左辺へ代入する」同時代入なので、aの古い値（$F(i-2)$）が先に消えてしまう心配がありません（ヒント 3 の安全な実現方法）。これで

• 時間計算量 $O(n)$：ループを $n-1$ 回実行するだけで済みます。
• 空間計算量 $O(1)$：変数a、bの 2 つしか使いません。

なぜ「再帰を使わずループで」なのか

章の本文では、フィボナッチ数列を「再帰木」の代表例として取り上げています。素朴な再帰

def fib_recur(n: int) -> int: if n == 1 or n == 2: return n - 1 # f(1) = 0, f(2) = 1 return fib_recur(n - 1) + fib_recur(n - 2)

（recursion.py を参照）はコードが簡潔ですが、$f(n)$ を求めるのに $f(n-1)$ と $f(n-2)$ をそれぞれ独立に再帰するため、呼び出しの総数は指数関数的に爆発し、時間計算量は $O(2^n)$ オーダーになります。同じ入力を何度も計算する重複が大量に発生するためです。

これに対し、ループ版はボトムアップに「前の 2 項から次の項を 1 回ずつ作る」ため、$O(n)$ 時間・$O(1)$ 空間で済みます。この「同じ部分問題を何度も解かない」という発想は、後の**動的計画法（DP）**の章（動的計画法イントロ）で「重複部分問題」として本格的に扱われるテーマであり、本章の演習はその布石になっています。実際、DP の入門では「フィボナッチの素朴再帰 → メモ化 → DP の順で計算量が改善される」流れが典型的な導入例として使われます。

実装と実行で確かめる：複数言語の自己テスト構成

演習コードは冒頭の Python ファイルだけでなく、リポジトリのja/codes/配下では Python・C++・Java・Go・C など複数の主要言語で同一ロジックが提供されています。たとえば C++ 版の complexity_exercises.cpp は、Python 版と同じsumIter/sumRecur/linearLoop/quadraticLoop/logarithmicLoopを実装し、main()内のassertで全関数の出力を検証しています。

assert(sumIter(1) == 1 && sumRecur(1) == 1); assert(sumIter(4) == 10 && sumRecur(4) == 10); assert(linearLoop(4) == 6); assert(quadraticLoop(4) == 20); assert(logarithmicLoop(4) == 1 && logarithmicLoop(5) == 1);

この「ファイルをそのまま実行すれば演習の正答を確認できる」構成は、複雑度の理論（紙上の計算）と実装の一致を体験するための設計です。ローカルで試す場合は、たとえば Python 版であればリポジトリのja/codes/pythonディレクトリで

python chapter_computational_complexity/complexity_exercises.py

を実行すると、assertがすべて通る（エラーを出さずに正常終了する）ことを確認できます。このときsum_iter(4) == sum_recur(4) == 10という検証は、まさに確認問題 1 で導いた「反復も再帰も $n=4$ で 10 を返す」という結論をコード上で裏付けています。

まとめ：章末演習が教える 4 つの「型」

日本語版の 章末演習 の内容を、本文とソースコードを照合しながら見てきました。この演習セットが鍛えてくれるのは、以下の 4 つの「型」です。

1. 再帰の空間コストを可視化する：時間計算量が同じ $O(n)$ でも、再帰は呼び出しスタックにより空間計算量が $O(n)$ になる。空間計算量の分析にはコード内の変数だけでなく再帰のスタックフレームも数える。
2. ループ構造から計算量を読む：線形ループは $O(n)$、二重ループは（内側の回数が減っても）$O(n^2)$、半分ずつ減るループは $O(\log n)$。計算量の順序 $O(\log n) < O(n) < O(n^2)$ は頻出の比較軸。
3. インプレース操作の代償を理解する：$O(1)$ 空間のインプレース反転は入力配列を破壊する。要件（入力を変更してよいか）に応じて $O(n)$ のコピー方式と使い分ける。
4. 再帰と反復の実務的判断：簡潔さと効率はトレードオフ。フィボナッチでは反復により $O(2^n)$ → $O(n)$ 時間、$O(n)$ → $O(1)$ 空間へ改善でき、その背後にある「重複部分問題」の視点は動的計画法の入り口となる。

理論の細部（各計算量階の定義、スタックフレームの仕組み、尾再帰の注意点など）を復習したい場合は、反復と再帰、時間計算量、空間計算量、そして 章のまとめ（Q&A つき） をあわせて読むことで、演習の答えが「丸暗記」ではなく「原理から導ける」状態になるはずです。

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo