| 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개 항목에 대한 하나의 루프 → 대략 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 코인 + 오늘 첫 완료 시 소액 보너스
입력 크기에 따른 연산 수를 세는 것 — 초는 기계에 따라 다름.