| English | 意味 |
|---|---|
| run time/rʌn taɪm/ | 実行時間 |
| linear/ˈlɪnɪə/ | 線形 |
| quadratic/kwɒˈdrætɪk/ | 二次 |
Counting the work
- We measure a program's run time 运行时间 by how many times its key statements run.
- Not seconds (those vary by machine) — a count of operations as the input grows.
- More operations for the same input size → slower algorithm.
- This lets us compare algorithms fairly, independent of hardware.
A single loop: about n
- A loop over
nitems runs its body aboutntimes. - Double the input → about double the work. This is linear 线性 growth.
- Summing an array, searching a list one-by-one: all about
nsteps. - Written informally as "order
n."
A nested loop: about n²
- A nested loop over
nitems runs its inner body aboutn × n = n²times. - Double the input → about four times the work. This is quadratic 二次 growth.
- Comparing all pairs, filling an
n × ngrid: aboutn²steps. n²grows much faster thannasngets large.
Comparing growth
- To compare algorithms, ask how the work grows as the input grows.
- For large
n, annalgorithm beats ann²algorithm — often by a lot. - Focus on the part of the code that runs the most (usually the innermost loop).
- The fastest-growing term dominates the total run time.
Judge run time by GROWTH, not a fixed count. An algorithm that does n steps and one that does 2n + 5 steps both grow linearly — for comparing, the constant and the +5 don't matter; the shape (n vs n²) does. A single loop is about n; a nested loop is about n², which grows far faster for large inputs.
Two ways to find duplicates in n items:
- Nested loops comparing every pair: about
n²steps. - Sort first, then one pass: far fewer steps for large
n. - For
n = 1000,n²is a million steps — then²approach is much slower.
Informal run-time analysis counts how many times statements run as the input grows. A single loop over n items is about n (linear); a nested loop is about n² (quadratic), which grows much faster. Compare algorithms by their growth, focusing on the most-executed (innermost) code.
nに対する作業量の成長
ネストループ(n²)は単一ループ(n)よりもはるかに速く成長します。
n個のアイテムに対する単一ループは、ボディを約何回実行しますか？
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
n個のアイテムに対する1つのループ → 約nステップ（線形）。
n個のアイテムに対するネストループは、内側のボディを約何回実行しますか？
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
n × n = n²（二次関数）。
n = 1000の場合、n²アルゴリズムは約何ステップ（百万単位）ですか？
難易度 2/5 · 140 コイン + 今日初回完了時に小ボーナス付与
1000² = 1,000,000 = 1百万。
大きなnに対して、nステップのアルゴリズムは一般的にn²ステップのアルゴリズムより速いです。
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
n²ははるかに速く成長するため、大きなnでははるかに多くの作業を行います。
実行時間を秒で測定しますが、これはすべてのコンピュータで同じではありません。
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
入力サイズに対する演算数を数えます — 秒数は機械によって異なります。