본문으로 건너뛰기
자료구조 · 알고리즘 기초집LESSON 02

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

난이도초급 → 중급 입문
예상 시간40분
선수지식이전 강의

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

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

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

2. 학습 목표​

3. 핵심 개념​

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

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));
    }
}

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. 자주 하는 실수와 해결법​

7. 직접 실습​

8. 이해 점검 질문 3개​

9. 핵심 요약​

MINI QUIZ

Big-O 복잡도 점검

선택 즉시 정답과 해설을 확인할 수 있습니다. 결과는 이 브라우저에만 저장됩니다.

0 / 2
  1. 문제 1입력 크기가 커질 때 일반적으로 더 잘 확장되는 시간 복잡도는 무엇인가요?
  2. 문제 2Big-O 표기법이 주로 설명하는 것은 무엇인가요?

답을 선택하면 진행 결과가 자동으로 저장됩니다.

LESSON STATUS

학습을 마쳤나요?

직접 실습과 점검 질문까지 확인한 뒤 완료로 표시하세요.

02강. 시간 복잡도와 공간 복잡도: Big-O를 읽는 법 미완료 상태