forループの実行回数を返す
10 倍のデータで、10 倍待たされるのか
「このコードは遅いですか」と聞かれても、眺めているだけでは答えられません。100 件なら一瞬で終わったのに、10 万件を流したら帰ってこない、ということが起きます。速いか遅いかを見分ける物差しは、実行時間そのものではなく ループが何回まわるか です。回数さえ数えられれば、データが増えたときに何が起きるかを、動かす前に見積もれます。
この章の入口として、まずは「n を渡したとき、ループ本体は本当に n 回動いているのか」を自分の手で数えます。当たり前に見えて、n が 0 のときや、条件式を 1 文字書き間違えたときに、この数はあっさりずれます。
i <= n と書くと、1 回多くまわる
Python の range(n) が返すのは 0 から n - 1 までで、合計 n 個です。実際に出してみます。
Python
for i in range(3):
print(i)
# 0
# 1
# 23 は出てきません。JavaScript の書き方も範囲は同じです。
JavaScript
for (let i = 0; i < 3; i++) {
console.log(i);
}
// 0, 1, 2ここで i <= n や i < n + 1 と書くと、本体は n + 1 回動きます。たった 1 回の差なので結果を見ても気づきにくく、配列を触るときに範囲外アクセスとして初めて表に出ます。n が 0 や負のときは 1 回もまわらない、という点もあわせて押さえてください。
一定なのか、比例するのか
処理には、データ量に関係なく終わるものと、データ量に引きずられるものがあります。
Python
def firstPrice(prices):
return prices[0]中身が 10 件でも 100 万件でも、やることは 1 回の取り出しだけです。かかる時間は変わりません。これを O(1) と書きます。
一方、全件に対して 1 回ずつ何かをする処理は、件数が 10 倍になれば時間もおよそ 10 倍になります。これが O(n) です。1 重のループはこの形の代表で、n がそのまま回数になります。
記法は 6 つ覚えれば足りる
| 記法 | 増え方 | 典型 |
|---|---|---|
O(1) | 増えない | 先頭の要素を取り出す |
O(log n) | 半分ずつ絞る | 並んだ中から絞り込む |
O(n) | 比例する | 1 重のループ |
O(n log n) | 比例より少し重い | 実用的な並べ替え |
O(n^2) | 2 乗で増える | 入れ子のループ |
O(2^n) | 手に負えない | 全部の組み合わせを試す |
1 ステップを 1 ナノ秒とすると、n が 10 億でも O(n) はおよそ 1 秒で終わります。同じ n で O(n^2) は数十年です。オーダーが 1 段違うだけで、現実の待ち時間は桁違いになります。
定数倍は無視するのが約束です。
n回でも2n回でもn / 2回でも、まとめてO(n)と書きます。見たいのは増え方だけだからです。
要件
- for ループを使って 0 から n-1 まで実行回数を数えること
- n <= 0 の場合は 0 を返すこと
- 戻り値は整数 (int) であること
入出力例
countIterations(5) → 5
countIterations(0) → 0
countIterations(1) → 1
countIterations(10) → 10
countIterations(100) → 100
countIterations(-3) → 0ヒント
