forループの実行回数を返す
forループの実行回数を返す
このレッスンで分かること
O(1)は一定、O(n)は比例、O(log n)は半分ずつ縮める、O(n^2)は 2 乗で増える- Python の
range(n)は0, 1, 2, ..., n-1まで合計n個の値を返します- プログラムが速いか遅いかを語るとき、
forループが 何回まわるか が最重要の指標になります
forループの実行回数を返す とは
for ループを n 回まわすときに、本当に n 回実行されているのかを自分の手で数え、計算量の感覚を掴む。
プログラムが速いか遅いかを語るとき、for ループが 何回まわるか が最重要の指標になります。本章ではアルゴリズムの効率を測る尺度として Big-O (オーダー記法) を扱いますが、その入口として、まずは「ループが本当に n 回実行されているか」を自分で数えてみましょう。
本レッスンの課題は、整数 n を受け取り、for i in range(n): のようなループを実行したとき、ループ本体が 何回実行されたか をカウントして返す関数を書くことです。当たり前のように見えますが、n = 0 や n = 1 の挙動、ループ変数の範囲をきちんと理解しているかが試されます。
ループ回数 = アルゴリズムの 実行時間の素 。まずは「1 重ループは
O(n)」という感覚を体に染み込ませよう。
range の挙動を正しく理解する
Python の range(n) は 0, 1, 2, ..., n-1 まで合計 n 個の値を返します。JavaScript で for (let i = 0; i < n; i++) と書いたときと同じ範囲です。つまり n = 5 なら 5 回、n = 0 なら 0 回まわります。これを正確に把握することが、計算量の議論の 大前提 です。
図のポイント (テキスト併記)
- 図のとおり、ループ本体は
i = 0からi = n-1までn回呼ばれます
図のとおり、ループ本体は i = 0 から i = n-1 まで n 回呼ばれます。終了時のカウンタは n になります。
O(n) の意味
計算量の表記 O(n) は「入力 n に比例した時間がかかる」ことを意味します。つまり n が 10 倍になると、おおむね処理時間も 10 倍になります。1 重の for ループは典型的な O(n) の処理です。
O(n)は「nに比例」。O(1)は「nに関係なく一定」。この 2 つの違いがすべての出発点。
Python での実装例
Python
def countIterations(n):
count = 0
for i in range(n):
count += 1
return count素直に count を 0 から始めて、ループの中で += 1 するだけです。n が 0 以下なら range が空になるので、count は 0 のままになります。
JavaScript での実装例
JavaScript
function countIterations(n) {
let count = 0;
for (let i = 0; i < n; i++) {
count += 1;
}
return count;
}i < n の条件式が大事で、i <= n と書いてしまうと 1 回多くまわってしまうバグの典型例になります。
よくある間違い
1 つ目は オフバイワン エラー (off-by-one) です。i <= n や i < n + 1 などと書いてしまい、n + 1 回実行されてしまうケースが頻発します。range(n) や i < n は厳密に n 回まわると覚えましょう。
2 つ目は 負の n や n = 0 を考慮しないケースです。n = 0 で count = 0 が返るかを必ず確認しましょう。n が負ならループは 1 回もまわらず 0 を返すのが自然な挙動です。
3 つ目は 戻り値を return し忘れる ケースです。print(count) で出力するだけでは executor は受け取れません。必ず return count で値を返してください。
やってみよう
n = 5を渡すと5が返ることを確認する。n = 1000000を渡したとき、処理がほぼ一瞬で終わることを体感する。これがO(n)の特徴です。- 次のレッスンでは入れ子ループを扱います。
n = 1000の 2 重ループは1000000回まわるのに対し、1 重ループはたったの1000回です。
ループの回数を数える練習は、計算量を見積もる 第一歩 。地味だがここで手を動かしておくと後が楽になる。
Java と Go での実装
Java や Go でも基本のロジックは同じです。for ループのカウンタを 0 から n - 1 まで動かし、本体で count を += 1 するだけです。
Java
public static int countIterations(int n) {
int count = 0;
for (int i = 0; i < n; i++) {
count += 1;
}
return count;
}Go
func countIterations(n int) int {
count := 0
for i := 0; i < n; i++ {
count += 1
}
return count
}どの言語でも i < n の条件式は変わりません。範囲の表現が range(n) か for i = 0; i < n; i++ かで違うだけで、挙動は同じです。
O(1) との対比
O(1) は「n に関係なく一定」の処理です。例えば「配列の先頭要素を返す arr[0]」や「2 つの数の和 a + b」は、データ量が増えても処理時間が変わらないため O(1) です。本問の countIterations(n) は n が大きくなるほど時間がかかるので O(n) 。この 入力サイズ依存 の感覚を最初に押さえておくと、後のオーダー比較が楽になります。
O(1)は一定、O(n)は比例、O(log n)は半分ずつ縮める、O(n^2)は 2 乗で増える。この 4 種類だけでもしっかり区別できれば実務で十分通用する。
計算量と実行時間の対応
仮に 1 ステップが 1 ナノ秒 かかるとすると、n = 10^9 (10 億) の O(n) 処理はおよそ 1 秒で終わります。O(n^2) だと 10^18 ステップ必要で、これは現実時間で数十年かかります。O(log n) なら n = 10^9 でも 30 ステップ。オーダーの違いは現実の時間で 億倍 の差 になりうる、というのが計算量を学ぶ最大の動機です。
よくある質問
Q. for と while はどう使い分けますか？
A. 繰り返し回数や対象が決まっているなら for（リスト・range など）が読みやすく、終了条件が動的に決まるなら while を使います。例えば「100 回繰り返す」は for i in range(100):、「ユーザー入力が q になるまで」は while True + break が向いています。
Q. ループの途中で抜けたいときは？
A. break を使うとそのループを即座に終了します。次の周回に進みたいだけなら continue を使い、現在の処理だけスキップします。break / continue は読み手にとってジャンプ先が見えにくいため、関数化して return で抜けると意図が伝わりやすくなります。
Q. インデックスも一緒に取りたい場合は？
A. Python なら for i, v in enumerate(items):、JavaScript なら items.forEach((v, i) => ...) のようにインデックスを同時に取り出せます。手動で i = 0; i += 1 と書くと off-by-one のミスを誘発しやすいので、言語の標準機能を使うのが安全です。
次のレッスン
次は 入れ子ループの実行回数 に進みましょう。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- ループの実行回数 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. ループの実行回数 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- for ループを使って 0 から n-1 まで実行回数を数えること
- n <= 0 の場合は 0 を返すこと
- 戻り値は整数 (int) であること
入出力例
test-cases.txt
countIterations(5) → 5
countIterations(0) → 0
countIterations(1) → 1
countIterations(10) → 10
countIterations(100) → 100
countIterations(-3) → 0