이 페이지는 최신 브라우저(SharedArrayBuffer 지원)가 필요합니다. Chrome, Edge, Firefox 또는 Safari를 최신 버전으로 업데이트해 주세요.
우리가 할 일
- 두 프로그램이 모두 정확하더라도 소요 **시간(time)**이 크게 다를 수 있습니다.
- 이 수업은 효율성(efficiency), 즉 입력 크기에 따라 작업량이 어떻게 증가하는지에 대해 다룹니다.
- 내용을 읽고 생각한 후, 몇 가지 짧은 과제를 통해 직접 단계(step)를 세어 볼 수 있습니다.
작업량 세기
- 알고리즘의 성능을 측정할 때 수행 단계(step)의 수를 기준으로 삼으며, 절대 시간(초)은 사용하지 않습니다.
- 초 단위의 단계 수는 컴퓨터 환경에 따라 달라지지만, 단계 자체를 세는 것은 그렇지 않습니다.
- 입력량이 증가하면 일반적으로 단계 수도 증가합니다. 문제는 얼마나 더 늘어나는가입니다.
합리적인 vs 비합리적인 실행 시간
- 적절한 시간이란 단계 수가 다항식으로 증가하거나 그보다 느리게 증가하는 것을 의미하며, 상수, 선형, 제곱 또는 세제곱 형태가 포함됩니다.
- 단일 루프는 선형이며, 루프 내부에 다른 루프가 있는 경우 제곱(n × n)이 됩니다. 제곱은 선형보다 빠르게 증가하지만 여전히 적절한 시간 범주에 속합니다.
- 부적절한 시간은 지수함수나 계승적 증대를 의미하며, 입력량이 조금만 늘어나면 작업량이 급격히 증가합니다.
English
Input size: 10 20 40
Search a list: 10 20 40 (linear - reasonable)
Nested loops: 100 400 1,600 (square - still reasonable)
Try all orders: 3,628,800 ... 48 digits (factorial - unreasonable)
작은 데모: 단계 세기
- 아래에서는 선형 탐색이 수행하는 비교 횟수를 세어 봅니다.
- 이 횟수는 리스트 크기와 함께 단계별로 증가하며, 느리고 일정한 성장을 보입니다.
- 크기를 변경해 보시면 그 변화에 따라 횟수가 어떻게 따르는지 확인할 수 있습니다.
English
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))
빠름만으로는 부족할 때
- 일부 문제에는 알려진 적절한 시간 내 해결 알고리즘이 없습니다.
- 정확한 방법은 모든 순서를 시도해 볼 수 있습니다. 이는 계승적 증대가므로 큰 입력량에는 부적절합니다.
- 히어리틱은 충분히 좋은 해를 제공할 수 있는 단축법입니다. 최선의 해임을 보장하지 않으며, 특정 하나의 히어리틱을 외울 필요는 없습니다.
결정 불가능한 문제(undecidable problems)
- 느리기는커녕: 일부 문제는 아무런 알고리즘으로도 해결할 수 없습니다.
- 이러한 문제들을 결정 불가능한 문제라고 부릅니다.
- 컴퓨터가 얼마나 빨라지더라도, 모든 경우에서 정확한 답을 줄 수 있는 프로그램은 존재하지 않습니다.
English
Reasonable : constant, linear, square or cube growth
Unreasonable : exponential or factorial growth
Undecidable : no algorithm can solve it for every input
기억해야 할 핵심 개념
- 효율성은 한 컴퓨터가 소요하는 초단위가 아니라, 단계 수의 증가 양상이 입력 크기에 따라 어떻게 변하는지에 관한 것입니다.
- 다항식 증대 이하의 형태는 적절한 시간입니다. 중첩 루프(n × n)도 여전히 적절한 시간 범주에 포함됩니다.
- 지수 함수적 또는 계승적 성장은 비현실적입니다. 일부 문제는 또한 결정 불가능합니다.
흔한 실수
- 중첩 루프를 부적절한 시간으로 간주해서는 안 되며, 제곱과 세제곱 증대는 여전히 적절한 시간입니다.
- 공식적인 Big-O 표기법을 시험 규칙으로 사용. Big-O는 출제되지 않음. 줄은 다항식 이하인지, 지수함수나 계승급 이상인지를 비교.
이제 직접 해보기
- 작업량이 어떻게 성장하는지 체감하기 위해 단계 수를 세는 작은 함수를 작성해 보십시오.
- Compare a single loop, a nested loop, and "try all orders". The nested loop is still reasonable time. Press Check answer.
탐색하기
알고리즘의 확장성
제곱 증가는 직선보다 빠르지만 여전히 합리적인 시간 범위에 속합니다. 계승 증가는 비합리적입니다.
난이도 3/5 · 200코인 + 오늘 첫 완료 시 작은 보너스 추가
선형 탐색이 수행하는 비교 횟수를 반환하는 scan_compares(data, target)을 작성하십시오. 각 항목을 target과 비교하며 매번 1씩 카운트하고, 발견하자마자 즉시 멈추십시오. 목록에 없다면 모든 항목을 비교하게 됩니다. 예시: scan_compares([5, 8, 2], 8) → 2.
출력을 보려면 '실행'을 클릭하세요.
난이도 3/5 · 200코인 + 오늘 첫 완료 시 작은 보너스 추가
루프 안에 루프를 사용하는(두 루프 모두 range(n)을 반복) pair_count(n)을 작성하여 안쪽 단계가 실행되는 횟수를 반환하십시오. 이는 n × n입니다. 예시: pair_count(3) → 9. 단일 루프보다 훨씬 빠르게 증가합니다.
출력을 보려면 '실행'을 클릭하세요.
난이도 3/5 · 200코인 + 오늘 첫 완료 시 작은 보너스 추가
n개의 항목을 배치할 수 있는 서로 다른 순서의 개수를 반환하는 count_orderings(n)을 작성하십시오. 즉, 1 × 2 × ... × n(n의 계승)입니다. count_orderings(0)은 1입니다. 예: count_orderings(3) → 6. 이 값이 얼마나 빠르게 증가하는지 주의하십시오: count_orderings(10)은 3 백만을 넘습니다.
출력을 보려면 '실행'을 클릭하세요.