시간복잡도와 공간복잡도에 대해 설명해 주세요.

알고리즘의 성능을 측정하는 두 가지 지표로, 시간복잡도는 실행 시간을, 공간복잡도는 메모리 사용량을 입력 크기 n에 대한 함수로 표현합니다.

Big-O 표기법

최악의 경우를 기준으로 상한선을 표현하는 점근적 표기법입니다.

성능 순서: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

시간복잡도

// O(1) - 입력 크기와 무관
int getFirst(int[] arr) {
    return arr[0];
}

// O(n) - 입력에 비례
int sum(int[] arr) {
    int total = 0;
    for (int x : arr) total += x; // n번 반복
    return total;
}

// O(n²) - 이중 루프
void printPairs(int[] arr) {
    for (int i = 0; i < arr.length; i++)       // n번
        for (int j = 0; j < arr.length; j++)   // n번
            System.out.println(arr[i] + ", " + arr[j]);
}

공간복잡도

// O(1) - 추가 메모리 고정
int sum(int[] arr) {
    int total = 0; // 변수 1개만 사용
    for (int x : arr) total += x;
    return total;
}

// O(n) - 입력 크기만큼 메모리 사용
int[] copyArray(int[] arr) {
    int[] copy = new int[arr.length]; // n 크기 배열 생성
    for (int i = 0; i < arr.length; i++) copy[i] = arr[i];
    return copy;
}

// O(n) - 재귀 호출 스택도 공간 차지
int factorial(int n) {
    if (n == 1) return 1;
    return n * factorial(n - 1); // 호출 스택 n개 쌓임
}

시간 vs 공간 트레이드오프

두 복잡도는 종종 반비례 관계로, 하나를 줄이면 다른 하나가 늘어납니다.