ALGORITHMS · CHAPTER 01
기초 · 40분시간 복잡도와 점근 표기
빠르다는 말을 수학적으로
반복문·중첩 반복문의 성장률을 Big-O로 추정한다.
한 줄 정의
O(f(n))는 n이 커질 때 지배적인 증가 경향을 본다.CONCEPTS
개념을 문장으로 설명하기
입력 크기 n
알고리즘이 처리해야 하는 데이터 양을 나타내는 변수입니다.
예시
학생 목록 탐색이라면 n은 학생 수가 될 수 있습니다.
CHECK실행 시간의 절대 초가 아니라 성장률을 본다.
지배항
n이 충분히 커졌을 때 가장 크게 영향을 주는 항입니다.
예시
3n² + 10n + 7은 n² 항이 지배하므로 O(n²)로 봅니다.
CHECK상수와 낮은 차수 항은 생략한다.
공간 복잡도
입력 외에 알고리즘이 추가로 사용하는 메모리의 성장률입니다.
예시
길이 n의 보조 배열을 만들면 보통 O(n) 추가 공간입니다.
CHECK시간과 공간을 함께 비교한다.
GUIDED PRACTICE
중첩 반복문 세기
for i in 0..n-1 안에서 for j in 0..n-1을 실행합니다.
- 바깥 반복이 n번 실행됩니다.
- 각 바깥 반복마다 안쪽 반복이 n번 실행됩니다.
- 총 기본 연산은 n × n = n²번입니다.
결론
시간 복잡도는 O(n²)입니다. n이 10배면 연산량은 대략 100배가 됩니다.
ACTIVE RECALL · 4 STEPS
가리고, 말하고, 확인하기
읽기만 하지 말고 답을 떠올린 뒤 펼쳐 보세요.
01 · 정의 회상
“입력 크기 n”을(를) 보지 않고 한 문장으로 정의해 보세요.
02 · 비교 설명
“지배항”이(가) 필요한 상황을 예시와 함께 설명해 보세요.
03 · 핵심 점검
시간과 공간을 함께 비교한다.
04 · 풀이 재현
“중첩 반복문 세기”의 결론을 보기 전에 풀이 순서를 3단계로 다시 적어 보세요.
WORKBOOK · STEP BY STEP
개념 확인 문제
정답을 고르고 해설로 사고 과정을 확인하세요.
01
3n² + 100n + 2의 Big-O는?
02
정렬된 배열을 절반씩 버리며 탐색하는 알고리즘의 전형적 시간 복잡도는?
03
입력 크기 n만큼의 보조 배열을 만들면 추가 공간은?
SPEAK IT OUT
면접 1분 답변 연습
Big-O가 실제 실행 시간을 완벽히 말해 주지 않는 이유와 그래도 유용한 이유를 설명해 보세요.
답변할 때는 정의 → 이유 → 짧은 예시 순서로 말해 보세요.공식·표준 자료로 더 읽기
Python docs · Time Complexity원문 열기 ↗자료구조 연산의 평균 시간 복잡도를 비교할 때 참고할 수 있습니다.