《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) 反復関数各ループ終了時のresn 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は各ループ終了時に次のように更新されます。ループ終了時iの値res累積和1 周目終了後112 周目終了後21 2 33 周目終了後33 3 64 周目終了後46 4 10したがって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 段階からなります反復と再帰の章。再帰呼び出しの過程sum_recur(4)は4 sum_recur(3)を計算するため、まずsum_recur(3)を呼び出します。同様に3 sum_recur(2)、2 sum_recur(1)と呼び出しが進みます。この時点ではどの関数もまだ値を返しておらず、4 回分の関数呼び出しがすべて「待機」状態です。終了条件の発動n 1に達すると1を返します基本ケース。復帰の過程呼び出しの逆順に結果が積み上げられ、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) 時間計算量と空間計算量の比較両者の計算量は以下のようにまとめられます。反復版sum_iter再帰版sum_recur時間計算量$O(n)$$n$ 回のループ$O(n)$$n$ 回の関数呼び出し空間計算量$O(1)$定数個の変数のみ$O(n)$呼び出しスタックに最大 $n$ 回分のフレーム時間計算量はどちらも $n$ に比例する回数のループ/呼び出しを行うため$O(n)$ で一致します。一方、空間計算量は大きく異なります。反復版が使う変数はresとiなど定数個であるため $O(1)$ です。再帰版は終了条件に達するまで、それ以前の関数呼び出しがすべて結果を待つ必要があります。システムは呼び出しごとに局所変数・呼び出し先アドレスなどを「スタックフレーム領域」に保存するため、最も深い時点で $n$ 回分のフレームが同時に存在し、空間計算量は $O(n)$ になります反復と再帰の章。この問題の最大の学びは、「空間計算量を分析するときはコード中の変数だけでなく、再帰呼び出しが占める空間も考慮する」という点です。再帰はコードを簡潔にしますが、関数呼び出しのオーバーヘッド時間とスタックフレーム空間というコストを伴うため、単純な総和のような問題では反復のほうが空間効率に優れます。これは章末の比較表「反復は通常、固定サイズのメモリを使う / 再帰はスタックフレーム領域を大量に使う可能性がある」とも整合します。確認問題 23 つのコード片の時間計算量を小さい順に並べる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)$時間計算量が小さい順に並べると次の通りです。順位コード片計算量理由1最小コード片 3$O(\log n)$ループのたびに $n$ が約半分になる2コード片 1$O(n)$ループはちょうど $n$ 回実行される3最大コード片 2$O(n^2)$内側ループの総実行回数が約 $n^2/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(n1)}{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 点に要約できます。$n$ が 0 と 1 の場合を先に処理する——これらは基本ケースで、それぞれ $F(0)0$、$F(1)1$ をそのまま返せます。数列全体を保存する必要はない——次の項の計算に必要なのは直前の 2 項だけです。配列で全項を持てば空間 $O(n)$ になりますが、2 変数の更新方式なら空間 $O(1)$ で済みます。古い値を先に上書きしない——たとえば「現在の項」を先に更新してしまうと、「次の項」の計算に必要な前の値が失われます。更新順序か同時代入に注意します。解答例Pythondef 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 ba, 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 で導いた「反復も再帰も $n4$ で 10 を返す」という結論をコード上で裏付けています。まとめ章末演習が教える 4 つの「型」日本語版の 章末演習 の内容を、本文とソースコードを照合しながら見てきました。この演習セットが鍛えてくれるのは、以下の 4 つの「型」です。再帰の空間コストを可視化する時間計算量が同じ $O(n)$ でも、再帰は呼び出しスタックにより空間計算量が $O(n)$ になる。空間計算量の分析にはコード内の変数だけでなく再帰のスタックフレームも数える。ループ構造から計算量を読む線形ループは $O(n)$、二重ループは内側の回数が減っても$O(n^2)$、半分ずつ減るループは $O(\log n)$。計算量の順序 $O(\log n) O(n) O(n^2)$ は頻出の比較軸。インプレース操作の代償を理解する$O(1)$ 空間のインプレース反転は入力配列を破壊する。要件入力を変更してよいかに応じて $O(n)$ のコピー方式と使い分ける。再帰と反復の実務的判断簡潔さと効率はトレードオフ。フィボナッチでは反復により $O(2^n)$ → $O(n)$ 時間、$O(n)$ → $O(1)$ 空間へ改善でき、その背後にある「重複部分問題」の視点は動的計画法の入り口となる。理論の細部各計算量階の定義、スタックフレームの仕組み、尾再帰の注意点などを復習したい場合は、反復と再帰、時間計算量、空間計算量、そして 章のまとめQA つき をあわせて読むことで、演習の答えが「丸暗記」ではなく「原理から導ける」状態になるはずです。【免费下载链接】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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
《Hello 算法》計算量解析の章末演習を徹底解説：反復と再帰・O記法の考え方を実例で身につける
《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) 反復関数各ループ終了時のresn 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は各ループ終了時に次のように更新されます。ループ終了時iの値res累積和1 周目終了後112 周目終了後21 2 33 周目終了後33 3 64 周目終了後46 4 10したがって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 段階からなります反復と再帰の章。再帰呼び出しの過程sum_recur(4)は4 sum_recur(3)を計算するため、まずsum_recur(3)を呼び出します。同様に3 sum_recur(2)、2 sum_recur(1)と呼び出しが進みます。この時点ではどの関数もまだ値を返しておらず、4 回分の関数呼び出しがすべて「待機」状態です。終了条件の発動n 1に達すると1を返します基本ケース。復帰の過程呼び出しの逆順に結果が積み上げられ、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) 時間計算量と空間計算量の比較両者の計算量は以下のようにまとめられます。反復版sum_iter再帰版sum_recur時間計算量$O(n)$$n$ 回のループ$O(n)$$n$ 回の関数呼び出し空間計算量$O(1)$定数個の変数のみ$O(n)$呼び出しスタックに最大 $n$ 回分のフレーム時間計算量はどちらも $n$ に比例する回数のループ/呼び出しを行うため$O(n)$ で一致します。一方、空間計算量は大きく異なります。反復版が使う変数はresとiなど定数個であるため $O(1)$ です。再帰版は終了条件に達するまで、それ以前の関数呼び出しがすべて結果を待つ必要があります。システムは呼び出しごとに局所変数・呼び出し先アドレスなどを「スタックフレーム領域」に保存するため、最も深い時点で $n$ 回分のフレームが同時に存在し、空間計算量は $O(n)$ になります反復と再帰の章。この問題の最大の学びは、「空間計算量を分析するときはコード中の変数だけでなく、再帰呼び出しが占める空間も考慮する」という点です。再帰はコードを簡潔にしますが、関数呼び出しのオーバーヘッド時間とスタックフレーム空間というコストを伴うため、単純な総和のような問題では反復のほうが空間効率に優れます。これは章末の比較表「反復は通常、固定サイズのメモリを使う / 再帰はスタックフレーム領域を大量に使う可能性がある」とも整合します。確認問題 23 つのコード片の時間計算量を小さい順に並べる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)$時間計算量が小さい順に並べると次の通りです。順位コード片計算量理由1最小コード片 3$O(\log n)$ループのたびに $n$ が約半分になる2コード片 1$O(n)$ループはちょうど $n$ 回実行される3最大コード片 2$O(n^2)$内側ループの総実行回数が約 $n^2/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(n1)}{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 点に要約できます。$n$ が 0 と 1 の場合を先に処理する——これらは基本ケースで、それぞれ $F(0)0$、$F(1)1$ をそのまま返せます。数列全体を保存する必要はない——次の項の計算に必要なのは直前の 2 項だけです。配列で全項を持てば空間 $O(n)$ になりますが、2 変数の更新方式なら空間 $O(1)$ で済みます。古い値を先に上書きしない——たとえば「現在の項」を先に更新してしまうと、「次の項」の計算に必要な前の値が失われます。更新順序か同時代入に注意します。解答例Pythondef 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 ba, 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 で導いた「反復も再帰も $n4$ で 10 を返す」という結論をコード上で裏付けています。まとめ章末演習が教える 4 つの「型」日本語版の 章末演習 の内容を、本文とソースコードを照合しながら見てきました。この演習セットが鍛えてくれるのは、以下の 4 つの「型」です。再帰の空間コストを可視化する時間計算量が同じ $O(n)$ でも、再帰は呼び出しスタックにより空間計算量が $O(n)$ になる。空間計算量の分析にはコード内の変数だけでなく再帰のスタックフレームも数える。ループ構造から計算量を読む線形ループは $O(n)$、二重ループは内側の回数が減っても$O(n^2)$、半分ずつ減るループは $O(\log n)$。計算量の順序 $O(\log n) O(n) O(n^2)$ は頻出の比較軸。インプレース操作の代償を理解する$O(1)$ 空間のインプレース反転は入力配列を破壊する。要件入力を変更してよいかに応じて $O(n)$ のコピー方式と使い分ける。再帰と反復の実務的判断簡潔さと効率はトレードオフ。フィボナッチでは反復により $O(2^n)$ → $O(n)$ 時間、$O(n)$ → $O(1)$ 空間へ改善でき、その背後にある「重複部分問題」の視点は動的計画法の入り口となる。理論の細部各計算量階の定義、スタックフレームの仕組み、尾再帰の注意点などを復習したい場合は、反復と再帰、時間計算量、空間計算量、そして 章のまとめQA つき をあわせて読むことで、演習の答えが「丸暗記」ではなく「原理から導ける」状態になるはずです。【免费下载链接】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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
