[CS-006][기초] 시간·공간복잡도로 코드 성장 읽기
페이지 정보
본문
[이번 수업]
입력 데이터가 커질 때 코드의 연산 횟수와 추가 메모리가 어떻게 늘어나는지 읽습니다. 실제 초 단위 속도와 복잡도 표기의 차이도 구분합니다.
[선수지식]
CS-002의 반복문, CS-003의 함수, CS-004의 리스트를 이해하면 됩니다.
[학습목표]
1. 입력 크기 n과 시간·공간복잡도의 관계를 설명한다.
2. O(1), O(log n), O(n), O(n log n), O(n²)의 성장 차이를 구분한다.
3. 연산 횟수와 추가 메모리 증가를 작은 코드로 확인한다.
[핵심개념]
복잡도는 알고리즘, 즉 문제를 푸는 절차가 입력 크기 n에 따라 얼마나 많은 자원을 요구하는지 나타냅니다. 시간복잡도는 실행에 필요한 연산의 증가를, 공간복잡도는 필요한 메모리의 증가를 살핍니다. 여기서 n은 목록의 원소 수처럼 문제 크기를 세는 값입니다.
Big-O(빅오)는 성장의 상한을 나타내는 표기입니다. 실무 학습에서는 큰 입력에서 지배적인 증가 형태를 비교하는 데 주로 씁니다. O(1)은 n이 커져도 작업량이 일정하고, O(log n)은 매 단계 탐색 범위를 크게 줄이며, O(n)은 입력만큼 한 번 훑습니다. O(n log n)은 효율적인 비교 정렬에서 자주 보이고, O(n²)은 모든 원소 쌍을 비교하는 중첩 반복에서 나타날 수 있습니다.
예를 들어 3n+10은 n이 충분히 커지면 n의 영향이 지배적이어서 O(n)으로 다룹니다. 다만 상수와 작은 항을 생략한다고 실제 성능까지 같다는 뜻은 아닙니다. 같은 O(n) 코드도 언어, 구현, 저장장치, 네트워크에 따라 측정 시간은 달라집니다. 최선·평균·최악 중 어느 경우인지도 함께 밝혀야 비교가 정확합니다.
공간을 볼 때는 입력 자체와 알고리즘이 새로 쓰는 보조 공간을 구분합니다. 기존 목록을 한 번 훑으며 합계를 내면 보조 공간은 대체로 O(1)이지만, 목록 전체를 복사하면 입력 크기에 비례하는 O(n) 보조 공간이 더 필요합니다. 시간과 공간은 서로 교환되기도 하므로 무조건 가장 작은 표기만 고르지 말고 데이터 크기와 자원 제한을 함께 봅니다.
[따라하기]
다음을 complexity_demo.py로 저장합니다. 단일 반복과 중첩 반복의 실행 횟수를 세고, 목록 복사 때 추적된 최대 메모리가 입력과 함께 커지는지 확인합니다.
```python
import tracemalloc
def operation_counts(n):
linear = 0
square = 0
for _ in range(n):
linear += 1
for _ in range(n):
for _ in range(n):
square += 1
return linear, square
def copy_peak(n):
values = [0] * n
tracemalloc.start()
copied = values[:]
_, peak = tracemalloc.get_traced_memory()
tracemalloc.stop()
return peak
for n in (10, 100):
linear, square = operation_counts(n)
print(f"n={n} linear={linear} square={square}")
print("copy memory grows:", copy_peak(10_000) < copy_peak(100_000))
```
macOS·Linux는 `python3 complexity_demo.py`, Windows는 `py complexity_demo.py`로 실행합니다. 예상 결과는 다음과 같습니다.
```text
n=10 linear=10 square=100
n=100 linear=100 square=10000
copy memory grows: True
```
n을 10배로 늘렸을 때 단일 반복은 10배, 중첩 반복은 100배가 됩니다. 메모리 바이트 수는 환경마다 달라질 수 있어 예제는 큰 복사가 더 많은지만 비교합니다. `tracemalloc`은 Python이 할당한 메모리 블록을 추적하는 진단 도구입니다.
[흔한 실수]
- Big-O를 실제 실행 시간의 초 단위 값으로 생각합니다.
- 작은 입력 한 번의 측정만 보고 알고리즘의 성장률을 단정합니다.
- 최악·평균·최선 조건을 말하지 않고 복잡도 하나만 적습니다.
- 입력 메모리와 복사·캐시·재귀 호출 같은 보조 공간을 섞어 셉니다.
[보안 주의]
크기 제한 없는 입력으로 O(n²) 작업이나 대량 복사를 실행하면 CPU·메모리 고갈로 서비스가 멈출 수 있습니다. 실습은 본인 소유의 로컬 환경에서 작은 n부터 늘리고, 운영 코드에는 입력 개수·파일 크기·처리 시간·메모리 상한을 둡니다. 외부 사용자가 n을 마음대로 키울 수 있는 경로는 인증과 요청 제한도 함께 적용하세요.
[직접 해볼 과제]
1. n에 1,000을 추가해 linear와 square 값을 예측한 뒤 실행 결과와 비교하세요.
2. 목록을 복사하지 않고 합계를 구하는 함수를 만들고, 그 보조 공간이 왜 O(1)인지 설명하세요.
[확인문제]
1. O(n²) 코드에서 n이 10배가 되면 대표 연산은 대략 몇 배가 되나요?
2. 같은 O(n)인 두 코드의 실제 실행 시간이 다를 수 있는 이유는 무엇인가요?
3. 입력 목록을 그대로 읽는 것과 전체 복사본을 만드는 것의 보조 공간 차이는 무엇인가요?
[다음 학습]
CS-007에서는 복잡도를 기준으로 정렬·검색 알고리즘을 비교합니다.
[공식 참고 자료]
- NIST Big-O 정의: https://www.nist.gov/dads/HTML/bigOnotation.html
- Python timeit 공식 문서: https://docs.python.org/3/library/timeit.html
- Python tracemalloc 공식 문서: https://docs.python.org/3/library/tracemalloc.html
입력 데이터가 커질 때 코드의 연산 횟수와 추가 메모리가 어떻게 늘어나는지 읽습니다. 실제 초 단위 속도와 복잡도 표기의 차이도 구분합니다.
[선수지식]
CS-002의 반복문, CS-003의 함수, CS-004의 리스트를 이해하면 됩니다.
[학습목표]
1. 입력 크기 n과 시간·공간복잡도의 관계를 설명한다.
2. O(1), O(log n), O(n), O(n log n), O(n²)의 성장 차이를 구분한다.
3. 연산 횟수와 추가 메모리 증가를 작은 코드로 확인한다.
[핵심개념]
복잡도는 알고리즘, 즉 문제를 푸는 절차가 입력 크기 n에 따라 얼마나 많은 자원을 요구하는지 나타냅니다. 시간복잡도는 실행에 필요한 연산의 증가를, 공간복잡도는 필요한 메모리의 증가를 살핍니다. 여기서 n은 목록의 원소 수처럼 문제 크기를 세는 값입니다.
Big-O(빅오)는 성장의 상한을 나타내는 표기입니다. 실무 학습에서는 큰 입력에서 지배적인 증가 형태를 비교하는 데 주로 씁니다. O(1)은 n이 커져도 작업량이 일정하고, O(log n)은 매 단계 탐색 범위를 크게 줄이며, O(n)은 입력만큼 한 번 훑습니다. O(n log n)은 효율적인 비교 정렬에서 자주 보이고, O(n²)은 모든 원소 쌍을 비교하는 중첩 반복에서 나타날 수 있습니다.
예를 들어 3n+10은 n이 충분히 커지면 n의 영향이 지배적이어서 O(n)으로 다룹니다. 다만 상수와 작은 항을 생략한다고 실제 성능까지 같다는 뜻은 아닙니다. 같은 O(n) 코드도 언어, 구현, 저장장치, 네트워크에 따라 측정 시간은 달라집니다. 최선·평균·최악 중 어느 경우인지도 함께 밝혀야 비교가 정확합니다.
공간을 볼 때는 입력 자체와 알고리즘이 새로 쓰는 보조 공간을 구분합니다. 기존 목록을 한 번 훑으며 합계를 내면 보조 공간은 대체로 O(1)이지만, 목록 전체를 복사하면 입력 크기에 비례하는 O(n) 보조 공간이 더 필요합니다. 시간과 공간은 서로 교환되기도 하므로 무조건 가장 작은 표기만 고르지 말고 데이터 크기와 자원 제한을 함께 봅니다.
[따라하기]
다음을 complexity_demo.py로 저장합니다. 단일 반복과 중첩 반복의 실행 횟수를 세고, 목록 복사 때 추적된 최대 메모리가 입력과 함께 커지는지 확인합니다.
```python
import tracemalloc
def operation_counts(n):
linear = 0
square = 0
for _ in range(n):
linear += 1
for _ in range(n):
for _ in range(n):
square += 1
return linear, square
def copy_peak(n):
values = [0] * n
tracemalloc.start()
copied = values[:]
_, peak = tracemalloc.get_traced_memory()
tracemalloc.stop()
return peak
for n in (10, 100):
linear, square = operation_counts(n)
print(f"n={n} linear={linear} square={square}")
print("copy memory grows:", copy_peak(10_000) < copy_peak(100_000))
```
macOS·Linux는 `python3 complexity_demo.py`, Windows는 `py complexity_demo.py`로 실행합니다. 예상 결과는 다음과 같습니다.
```text
n=10 linear=10 square=100
n=100 linear=100 square=10000
copy memory grows: True
```
n을 10배로 늘렸을 때 단일 반복은 10배, 중첩 반복은 100배가 됩니다. 메모리 바이트 수는 환경마다 달라질 수 있어 예제는 큰 복사가 더 많은지만 비교합니다. `tracemalloc`은 Python이 할당한 메모리 블록을 추적하는 진단 도구입니다.
[흔한 실수]
- Big-O를 실제 실행 시간의 초 단위 값으로 생각합니다.
- 작은 입력 한 번의 측정만 보고 알고리즘의 성장률을 단정합니다.
- 최악·평균·최선 조건을 말하지 않고 복잡도 하나만 적습니다.
- 입력 메모리와 복사·캐시·재귀 호출 같은 보조 공간을 섞어 셉니다.
[보안 주의]
크기 제한 없는 입력으로 O(n²) 작업이나 대량 복사를 실행하면 CPU·메모리 고갈로 서비스가 멈출 수 있습니다. 실습은 본인 소유의 로컬 환경에서 작은 n부터 늘리고, 운영 코드에는 입력 개수·파일 크기·처리 시간·메모리 상한을 둡니다. 외부 사용자가 n을 마음대로 키울 수 있는 경로는 인증과 요청 제한도 함께 적용하세요.
[직접 해볼 과제]
1. n에 1,000을 추가해 linear와 square 값을 예측한 뒤 실행 결과와 비교하세요.
2. 목록을 복사하지 않고 합계를 구하는 함수를 만들고, 그 보조 공간이 왜 O(1)인지 설명하세요.
[확인문제]
1. O(n²) 코드에서 n이 10배가 되면 대표 연산은 대략 몇 배가 되나요?
2. 같은 O(n)인 두 코드의 실제 실행 시간이 다를 수 있는 이유는 무엇인가요?
3. 입력 목록을 그대로 읽는 것과 전체 복사본을 만드는 것의 보조 공간 차이는 무엇인가요?
[다음 학습]
CS-007에서는 복잡도를 기준으로 정렬·검색 알고리즘을 비교합니다.
[공식 참고 자료]
- NIST Big-O 정의: https://www.nist.gov/dads/HTML/bigOnotation.html
- Python timeit 공식 문서: https://docs.python.org/3/library/timeit.html
- Python tracemalloc 공식 문서: https://docs.python.org/3/library/tracemalloc.html
- 이전글[TOOL-006][기초] 원격 저장소와 Pull Request로 협업하기 26.09.01
- 다음글[CORE-006][기초] 프로그램·프로세스·서비스 쉽게 구분하기 26.09.01
댓글목록
등록된 댓글이 없습니다.