Algorithmic efficiency
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · 이 페이지는 최신 브라우저(SharedArrayBuffer 지원)가 필요합니다. Chrome, Edge, Firefox 또는 Safari를 최신 버전으로 업데이트해 주세요.
English
What we'll do
- Two programs can both be correct but take very different time.
- This lesson is about efficiency: how the work grows as the input grows.
- Read and think about the ideas; then a few short tasks let you count the steps yourself.
한국어
우리가 할 일
- 두 프로그램이 모두 정확하더라도 소요 **시간(time)**이 크게 다를 수 있습니다.
- 이 수업은 효율성(efficiency), 즉 입력 크기에 따라 작업량이 어떻게 증가하는지에 대해 다룹니다.
- 내용을 읽고 생각한 후, 몇 가지 짧은 과제를 통해 직접 단계(step)를 세어 볼 수 있습니다.
English
Counting the work
- We measure an algorithm by how many steps it does, not seconds.
- Steps in seconds depend on the computer; counting steps does not.
- More input usually means more steps. The question is how much more.
한국어
작업량 세기
- 알고리즘의 성능을 측정할 때 수행 단계(step)의 수를 기준으로 삼으며, 절대 시간(초)은 사용하지 않습니다.
- 초 단위의 단계 수는 컴퓨터 환경에 따라 달라지지만, 단계 자체를 세는 것은 그렇지 않습니다.
- 입력량이 증가하면 일반적으로 단계 수도 증가합니다. 문제는 얼마나 더 늘어나는가입니다.
English
Reasonable vs unreasonable run time
- Some algorithms grow slowly: double the input, do about double the work.
- Some algorithms grow fast: a little more input means a huge jump in work.
- "Reasonable" run time grows slowly enough to finish; "unreasonable" blows up.
한국어
합리적인 vs 비합리적인 실행 시간
- 일부 알고리즘은 천천히 성장합니다: 입력량을 두 배로 늘리면 작업량도 약 두 배가 됩니다.
- 일부 알고리즘은 빠르게 성장합니다: 입력량이 조금만 늘어나면 작업량이 급격히 커집니다.
- "적정" 실행 시간은 충분히 천천히 성장하여 완수되지만, "부적정" 실행 시간은 폭발적으로 증가합니다.
Input size: 10 20 40
Search a list: 10 20 40 (slow growth - reasonable)
Try all orders: 3,628,800 ... a number with 48 digits (explodes!)
English
A tiny demo: counting steps
- Below we count the comparisons a linear search makes.
- The count grows in step with the list size — slow, steady growth.
- Try changing the size to see the count follow it.
한국어
작은 데모: 단계 세기
- 아래에서는 선형 탐색이 수행하는 비교 횟수를 세어 봅니다.
- 이 횟수는 리스트 크기와 함께 단계별로 증가하며, 느리고 일정한 성장을 보입니다.
- 크기를 변경해 보시면 그 변화에 따라 횟수가 어떻게 따르는지 확인할 수 있습니다.
def count_steps(n):
steps = 0
data = list(range(n))
target = -1 # not in the list, so we scan everything
for item in data:
steps = steps + 1
if item == target:
break
return steps
print(count_steps(10))
print(count_steps(20))
print(count_steps(40))
English
When fast is not enough
- Some problems have no known fast algorithm.
- The only methods try a huge number of possibilities — too slow for big input.
- For these, we often accept a good-enough answer instead of the perfect one.
한국어
빠름만으로는 부족할 때
- 일부 문제에는 알려진 빠른 알고리즘이 없습니다.
- 유일한 방법들은 방대한 수의 가능성을 시도하지만, 큰 입력량에는 너무 느립니다.
- 이러한 경우에는 완벽한 해답 대신 충분히 좋은 해답을 받아들이는 경우가 많습니다.
English
Undecidable problems
- Worse than slow: some problems cannot be solved by any algorithm at all.
- These are called undecidable problems.
- No matter how fast computers get, no program can always give the right answer.
한국어
결정 불가능한 문제(undecidable problems)
- 느리기는커녕: 일부 문제는 아무런 알고리즘으로도 해결할 수 없습니다.
- 이러한 문제들을 결정 불가능한 문제라고 부릅니다.
- 컴퓨터가 얼마나 빨라지더라도, 모든 경우에서 정확한 답을 줄 수 있는 프로그램은 존재하지 않습니다.
Fast : finishes quickly, even for big input
Slow but doable : finishes, but may take a very long time
Undecidable : no algorithm can solve it for every input
English
Key ideas to remember
- Efficiency is about how work grows with input size.
- Slow-growing algorithms scale to big inputs; fast-growing ones do not.
- Some problems are unreasonable to solve exactly, and some are undecidable.
한국어
기억해야 할 핵심 개념
- 효율성은 작업량이 입력 크기에 따라 어떻게 성장하는가에 관한 것입니다.
- 느리게 성장하는 알고리즘은 큰 입력량에도 확장 가능하지만, 빠르게 성장하는 알고리즘은 그렇지 못합니다.
- 정확히 해결하기 부적절한 문제가存在一些, 그리고 결정 불가능한 문제들이 있습니다.
English
Common mistakes
- Big-O describes how the running time GROWS with the input size.
- A reasonable-time algorithm scales; an unreasonable one does not.
한국어
흔한 실수
- Big-O 표기법은 실행 시간이 입력 크기에 따라 어떻게 성장하는가를 설명합니다.
- 적정 시간 알고리즘은 확장 가능하지만, 부적정 시간 알고리즘은 그렇지 못합니다.
English
Now you try
- Write small functions that count steps to feel how the work grows.
- Compare a single loop, a nested loop, and "try all orders". Press Check answer.
한국어
이제 직접 해보기
- 작업량이 어떻게 성장하는지 체감하기 위해 단계 수를 세는 작은 함수를 작성해 보십시오.
- 단일 루프, 중첩 루프, "모든 순열 시도"를 비교해 보십시오. 정답 확인 버튼을 누르십시오.
Explore · 탐색하기
How algorithms scale
As input grows, O(n²) explodes while O(log n) barely moves.
Write scan_compares(data, target) that returns how many comparisons a linear search makes. Compare each item to target, counting one each time, and stop as soon as you find it. If it is not in the list, you compared every item. Example: scan_compares([5, 8, 2], 8) → 2.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.
Write pair_count(n) that uses a loop inside a loop (both over range(n)) and returns how many times the inner step runs. This is n × n. Example: pair_count(3) → 9. This grows much faster than a single loop.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.
Write count_orderings(n) that returns how many different orders n items can be placed in — that is 1 × 2 × ... × n (n factorial). count_orderings(0) is 1. Example: count_orderings(3) → 6. Notice how fast it explodes: count_orderings(10) is over 3 million.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.