02강. 시간 복잡도와 공간 복잡도: Big-O를 읽는 법

?1. 이번 강의에서 해결할 문제

작은 샘플에서 1ms가 나온 코드도 입력이 커지면 멈춘 것처럼 보일 수 있습니다. 특정 PC의 측정값만 보지 않고 입력 크기에 따른 증가율로 풀이를 비교해야 합니다.

✓2. 학습 목표

✓이 강의를 마치면

• O(1), O(log n), O(n), O(n log n), O(n²)을 구분합니다.
• 최선·평균·최악 상황을 나누어 설명합니다.
• 시간과 추가 공간 사이의 교환 관계를 판단합니다.

◇3. 핵심 개념

Big-O는 입력 크기 n이 커질 때 연산량 증가의 상한을 단순화해 표현합니다. 상수와 낮은 차수는 제거하지만 실제 실행 시간이 같다는 뜻은 아닙니다. 배열 인덱스 접근은 O(1), 이진 탐색은 O(log n), 전체 순회는 O(n), 효율적인 비교 정렬은 보통 O(n log n), 모든 쌍 비교는 O(n²)입니다. 해시 조회처럼 입력 분포에 따라 달라지는 연산은 평균과 최악을 함께 적습니다. 공간 복잡도는 입력 자체를 제외한 보조 배열·재귀 스택·색인 메모리를 구분해 기록합니다.

용어 정리와 읽는 순서

• 입력 크기 n: 알고리즘이 처리할 항목 수입니다. 이 강의에서는 scores.length입니다.
• 시간 복잡도: 입력이 커질 때 비교·대입 같은 연산 횟수가 얼마나 빠르게 늘어나는지 나타냅니다.
• 공간 복잡도: 입력 외에 임시로 더 필요한 메모리가 얼마나 늘어나는지 나타냅니다.
• 최선·평균·최악: 같은 크기의 입력이라도 값의 순서에 따라 빨리 끝나거나 끝까지 실행될 수 있어 상황을 나눈 것입니다.

Big-O는 “O(n)은 1초”라는 시간이 아닙니다. 예를 들어 매 원소를 한 번 보는 O(n)은 n이 10배가 되면 핵심 연산도 대략 10배가 됩니다. 모든 서로 다른 쌍을 보는 O(n²)은 대략 100배가 됩니다.

n	O(1)	O(n)	O(n²)의 대략적인 쌍 비교 수 n(n-1)/2
10	1	10	45
100	1	100	4,950
1,000	1	1,000	499,500

낮은 차수와 상수를 생략하는 이유는 입력이 매우 커졌을 때 어떤 항이 증가를 지배하는지 보기 위해서입니다. 그렇다고 작은 입력에서도 언제나 Big-O가 낮은 코드가 빠르다는 뜻은 아닙니다. 실제 제품에서는 증가율 분석 뒤 대표 데이터로 측정합니다.

✎4. 단계별 실습

1. 예제 파일 작성

실행 환경: 코드 편집기

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: 같은 이름의 파일이 있다면 덮어쓰기 전에 Git diff로 변경 범위를 확인합니다. 선택한 LTS JDK의 java -version과 javac -version이 모두 실행되어야 합니다.

대상 파일: src/ComplexityDemo.java

src/ComplexityDemo.java

public class ComplexityDemo {
    static int findMax(int[] scores) {
        int max = Integer.MIN_VALUE;
        for (int score : scores) max = Math.max(max, score);
        return max;
    }

    static boolean hasDuplicateSlow(int[] scores) {
        for (int i = 0; i < scores.length; i++) {
            for (int j = i + 1; j < scores.length; j++) {
                if (scores[i] == scores[j]) return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] scores = {900, 1200, 700, 1200};
        System.out.println("최댓값: " + findMax(scores));
        System.out.println("중복: " + hasDuplicateSlow(scores));
    }
}

코드와 반복 횟수 추적

findMax의 for는 점수 네 개를 정확히 네 번 읽습니다. max는 다음 순서로 바뀝니다.

읽은 점수	변경 전 max	변경 후 max
900	가장 작은 정수	900
1200	900	1200
700	1200	1200
1200	1200	1200

hasDuplicateSlow는 i가 가리키는 값과 그 뒤의 값만 비교합니다. 같은 쌍을 반대 순서로 다시 보지 않고 자기 자신과도 비교하지 않기 때문에 j = i + 1에서 시작합니다. 현재 입력은 첫 번째 1200과 마지막 1200을 만났을 때 true로 조기 종료합니다.

2. PowerShell에서 컴파일·실행

실행 환경: Windows PowerShell

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: src/ComplexityDemo.java가 저장되었고 out 폴더에는 삭제해도 되는 컴파일 결과만 있는지 확인합니다.

대상: src/ComplexityDemo.java와 out 아래 생성되는 class 파일

Windows PowerShell

Set-Location C:\dev\game-ranking-algorithms
New-Item -ItemType Directory -Force .\out | Out-Null
javac -Xlint:all -d .\out .\src\ComplexityDemo.java
java -cp .\out ComplexityDemo

예상 결과: 출력의 라벨과 값까지 다음과 같은지 확인합니다.

최댓값: 1200
중복: true

실행 시간은 PC의 CPU·메모리, JDK 버전, JVM 워밍업, 백그라운드 작업과 입력 분포에 따라 달라질 수 있습니다. 측정값은 같은 조건에서 여러 번 비교하고 Big-O 분석과 함께 해석합니다.

→5. 코드와 알고리즘이 동작하는 이유

findMax는 원소 수와 관계없이 각 값을 정확히 한 번 보므로 최선·평균·최악 모두 O(n), 추가 공간 O(1)입니다. 중복 검사는 중복이 앞에 있으면 일찍 끝나는 최선 O(1)이 가능하지만, 중복이 없거나 끝에 있으면 약 n(n-1)/2쌍을 확인해 최악 O(n²)입니다. 실제 시간은 CPU, JVM 워밍업, JDK, 백그라운드 작업에 따라 달라지므로 단일 측정값을 Big-O의 증거로 사용하지 않습니다.

!6. 자주 하는 실수와 해결법

!자주 하는 실수

• 실수: Big-O를 실제 초 단위 시간으로 이해하기 해결: 증가율 표기와 벤치마크 측정값을 구분합니다.
• 실수: 반복문 하나면 언제나 O(n)이라고 판단하기 해결: 반복 범위와 중첩, 조기 종료 조건을 계산합니다.
• 실수: 시간만 줄이고 메모리 증가를 기록하지 않기 해결: 보조 구조와 재귀 호출 스택도 공간 복잡도에 포함합니다.

✎7. 직접 실습

실습 목표

입력 값과 크기를 바꾸며 실제 반복 흐름을 확인하고, 빠른 중복 검사가 추가 메모리를 사용하는 이유를 설명합니다.

시작 전 상태

위 예제를 한 번 실행한 뒤 종이에 findMax와 hasDuplicateSlow의 예상 비교 횟수를 먼저 적습니다. 측정값보다 예측을 먼저 남겨야 결과를 설명할 수 있습니다.

1단계: 가장 작은 변경 — 조기 종료 없애기

입력을 {900, 1200, 700, 1500}으로 바꿉니다. 중복이 없으므로 네 원소의 모든 쌍, 즉 6쌍을 확인하고 false가 나와야 합니다. 비교 직전에 임시 comparisons++를 넣으면 예상 횟수를 눈으로 확인할 수 있습니다.

2단계: 값을 바꾸고 결과 비교

중복 값을 배열의 처음 두 칸에 놓은 경우와 마지막 두 칸에 놓은 경우를 각각 실행합니다. 둘 다 답은 true지만 비교 횟수는 다릅니다. 이것이 같은 알고리즘에서도 입력 분포에 따라 최선·평균·최악을 구분하는 이유입니다.

3단계: 직접 적용 — HashSet으로 중복 검사

HashSet<Integer>에 점수를 하나씩 추가하고, add가 false를 반환하면 중복이라고 판단하는 메서드를 작성합니다. 일반적인 해시 분포에서 시간은 평균 O(n)으로 줄지만 최악에는 원소 수만큼의 추가 공간을 사용합니다.

✎직접 실습

• 느린 방식과 HashSet 방식이 빈 배열, 중복 없는 배열, 중복 있는 배열에서 같은 답을 내는지 확인합니다.
• 입력 10, 100, 1,000일 때 O(n²)의 최대 쌍 수를 표로 적습니다.
• 시간뿐 아니라 HashSet에 저장되는 원소 수도 기록합니다.

4단계: 스스로 확인

• “반복문 두 개이므로 무조건 O(n²)”가 아니라 실제 반복 범위를 식으로 설명했나요?
• 빠른 방식이 지불하는 추가 메모리를 적었나요?
• JVM 워밍업, JDK 버전, 백그라운드 작업처럼 측정에 영향을 주는 조건을 세 가지 이상 고정했나요?

막혔을 때

증상	원인	해결
비교 횟수가 예상보다 1 작음	return true 뒤에 횟수를 증가시킴	실제 비교 직전에 카운터를 증가시킵니다.
HashSet 방식이 항상 중복이라고 판단	add 반환 의미를 반대로 해석	새 값이면 true, 이미 있으면 false입니다.
짧은 실행 시간이 매번 크게 다름	JVM 준비 비용과 환경 잡음	같은 입력을 여러 번 실행하고 첫 결과만으로 결론 내리지 않습니다.

실습 기록에는 입력 크기, 예상 결과, 실제 결과, 시간·공간 복잡도와 사용한 JDK 버전을 함께 남깁니다.

?8. 이해 점검 질문 3개

?이해 점검

1. O(n log n)과 O(n²)의 차이는 입력이 커질수록 어떻게 나타나나요?
2. 조기 종료가 가능한 알고리즘은 어떤 상황별 복잡도를 적어야 하나요?
3. Big-O가 실제 실행 시간을 정확히 예측하지 않는 이유는 무엇인가요?

■9. 핵심 요약

■핵심 요약

Big-O는 하드웨어와 독립적으로 증가율을 비교하는 도구입니다. 최선·평균·최악 시간과 보조 공간을 구분하고, 실제 성능 측정은 별도의 검증으로 다룹니다.

다음 강의 연결

다음 강의에서는 고정된 스테이지 목표와 계속 늘어나는 플레이 기록을 배열과 ArrayList에 나누어 담으며 복잡도를 실제 구조 선택에 적용합니다.