시간복잡도와 공간복잡도 읽는 법

입력이 작은 예제에서는 어떤 코드든 빨라 보입니다. 그래서 복잡도 표기가 멀게 느껴질 수 있습니다. 하지만 입력이 커지면 같은 정답 코드도 통과와 시간 초과로 갈립니다.

복잡도는 공식을 외우는 과목이 아니라 증가 속도를 읽는 도구입니다. 입력이 10배가 될 때 시간과 메모리가 몇 배로 늘어나는지 미리 예상하게 도와줍니다. 여기서는 식 암기보다, 코드에서 반복이 어디서 늘어나는지 직접 읽는 연습을 합니다.

핵심 원리 요약

복잡도는 수식 암기 과목이 아니라 증가 속도를 읽는 도구입니다. 아래 세 용어를 읽으면서, 지금 보는 코드에서 반복이 몇 겹인지 바로 표시해 보세요.

시간복잡도는 입력이 커질 때 연산 횟수가 얼마나 빨리 늘어나는지 보여 줍니다. 정확히는 입력 크기 N에 대해 연산 수의 점근적 상한을 함수 형태로 나타낸 값입니다. 예를 들어 이중 루프는 입력이 2배로 늘면 비교 횟수가 대략 4배로 늘어 O(N^2) 성향을 보입니다.

공간복잡도는 입력 외에 추가 메모리가 얼마나 필요한지 나타냅니다. 정의로 보면 보조 저장공간이 N에 따라 어떤 비율로 증가하는지를 기술한 지표입니다. 길이 N 보조 배열 하나를 만들면 추가 공간이 N에 비례하므로 O(N)으로 표현합니다.

Big-O는 큰 입력에서 성능을 지배하는 항만 남겨 표기하는 약속입니다. 상수배와 하위차항을 제거하고 점근적 증가 상한만 기록하는 방식이라고 이해하면 충분합니다. 3N^2 + 10N + 7은 큰 N에서 N^2 항이 지배하므로 O(N^2)로 씁니다.

복잡도 해석이 운영 성능에 미치는 영향

복잡도 해석 능력이 없으면 다음 같은 실수가 반복됩니다.

테스트 데이터에서는 빠르지만 운영 데이터에서 급격히 느려짐
메모리 제한을 넘겨 런타임 오류 발생
문제의 핵심 병목을 잘못 진단해 최적화 방향을 놓침

복잡도는 어디를 고쳐야 성능이 실제로 개선되는지를 알려주는 지표입니다. 지금 최근 코드 하나를 골라, 반복문/재귀가 몇 겹인지 우선 표시해 보세요.

연산 횟수 추적 디버깅 시나리오

여기서는 오답 -> 디버깅 -> 교정 -> 검증 흐름으로 추적해, 어디서 불변식이 깨지는지 단계별로 확인합니다.

작은 입력으로 연산 횟수를 직접 세면 복잡도 감각이 빠르게 잡힙니다.

입력 예시: nums=[3,1,4,2], N=4
목표: nums[i] < nums[j]가 참인 쌍 개수 계산

i=0일 때 j=1..3을 비교해 3번 연산합니다.
i=1일 때 j=2..3을 비교해 2번 연산합니다.
i=2일 때 j=3만 비교해 1번 연산합니다.
총 비교 횟수는 3+2+1=6, 일반화하면 N(N-1)/2이므로 O(N^2)입니다.

이중 루프 비용 계산

문제 의도: 이중 루프가 만드는 비교 횟수를 코드 수준에서 확인합니다.
입력 예시: nums=[3,1,4,2]
출력 예시: 3 for가 두 겹이면 바깥 한 번마다 안쪽이 다시 처음부터 돈다는 점을 눈으로 확인해 보세요.

main.cpp

#include <iostream>
#include <vector>
using namespace std;

int pairCount(const vector<int>& nums) {
    int count = 0;
    int n = static_cast<int>(nums.size());
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (nums[i] < nums[j]) count++;
        }
    }
    return count;
}

int main() {
    cout << pairCount({3, 1, 4, 2}) << "\n";
    return 0;
}

Main.java

public class Main {
    static int pairCount(int[] nums) {
        int count = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] < nums[j]) count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(pairCount(new int[]{3, 1, 4, 2}));
    }
}

main.py

def pair_count(nums):
    count = 0
    n = len(nums)

    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] < nums[j]:
                count += 1

    return count

print(pair_count([3, 1, 4, 2]))  # 3

main.rs

fn pair_count(nums: &[i32]) -> i32 {
    let mut count = 0;
    let n = nums.len();
    for i in 0..n {
        for j in (i + 1)..n {
            if nums[i] < nums[j] {
                count += 1;
            }
        }
    }
    count
}

fn main() {
    println!("{}", pair_count(&[3, 1, 4, 2]));
}

복잡도 해석 결과 기초 조건 확인

바깥 루프는 N회, 안쪽 루프는 평균적으로 N/2회 수준으로 반복됩니다.
전체 비교 횟수는 대략 N(N-1)/2이므로 시간복잡도는 O(N^2)입니다.
추가 메모리는 count, n, 인덱스 변수뿐이므로 O(1)입니다.

평균 시간복잡도: O(N^2)
최악 시간복잡도: O(N^2)
공간복잡도: O(1)

정렬 기반 개선

문제 의도: 정렬 + 이진 탐색을 써도 삽입 비용 때문에 상한이 유지되는 경우를 보여줍니다.
입력 예시: nums=[3,1,4,2]
출력 예시: 3 insert는 중간에 값을 끼워 넣는 연산이라 뒤 원소가 밀리며 비용이 커집니다.

main.cpp

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int pairCountSorted(const vector<int>& nums) {
    vector<int> sortedPrefix;
    int count = 0;

    for (int x : nums) {
        auto it = upper_bound(sortedPrefix.begin(), sortedPrefix.end(), x);
        int pos = static_cast<int>(it - sortedPrefix.begin());
        count += static_cast<int>(sortedPrefix.size()) - pos;
        sortedPrefix.insert(it, x);
    }

    return count;
}

int main() {
    cout << pairCountSorted({3, 1, 4, 2}) << "\n";
    return 0;
}

Main.java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static int upperBound(List<Integer> arr, int target) {
        int lo = 0, hi = arr.size();
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr.get(mid) <= target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    static int pairCountSorted(int[] nums) {
        List<Integer> sortedPrefix = new ArrayList<>();
        int count = 0;
        for (int x : nums) {
            int pos = upperBound(sortedPrefix, x);
            count += sortedPrefix.size() - pos;
            sortedPrefix.add(pos, x);
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(pairCountSorted(new int[]{3, 1, 4, 2}));
    }
}

main.py

def upper_bound(arr, target):
    lo = 0
    hi = len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo

def pair_count_sorted(nums):
    sorted_prefix = []
    count = 0

    for x in nums:
        pos = upper_bound(sorted_prefix, x)
        count += len(sorted_prefix) - pos
        sorted_prefix.insert(pos, x)

    return count

print(pair_count_sorted([3, 1, 4, 2]))  # 3

main.rs

fn upper_bound(arr: &[i32], target: i32) -> usize {
    let mut lo = 0usize;
    let mut hi = arr.len();
    while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if arr[mid] <= target {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    lo
}

fn pair_count_sorted(nums: &[i32]) -> i32 {
    let mut sorted_prefix: Vec<i32> = Vec::new();
    let mut count = 0i32;

    for &x in nums {
        let pos = upper_bound(&sorted_prefix, x);
        count += (sorted_prefix.len() - pos) as i32;
        sorted_prefix.insert(pos, x);
    }

    count
}

fn main() {
    println!("{}", pair_count_sorted(&[3, 1, 4, 2]));
}

복잡도 해석 결과 전개 흐름 추적

이 구현은 이진 탐색(bisect_right)을 사용하지만, 리스트 중간 삽입이 O(N)입니다.
따라서 전체적으로는 여전히 O(N^2)입니다.
겉보기에는 고급 도구를 썼어도 자료구조 특성 때문에 상한이 바뀌지 않는 대표 사례입니다.

평균 시간복잡도: O(N^2)
최악 시간복잡도: O(N^2)
공간복잡도: O(N)

복잡도 도출 절차

문제를 풀 때 다음 순서로 분석하면 오류가 줄어듭니다.

1단계: 반복문/재귀 호출 횟수를 분리해 계산
2단계: 각 반복에서 수행하는 연산 비용 확인
3단계: 자료구조 연산(삽입/삭제/탐색)의 실제 비용 반영
4단계: 평균/최악/공간복잡도를 각각 기록

코드 길이보다 연산 패턴이 복잡도를 결정합니다.

정렬 선행 여부의 구현 비용 상충

복잡도 비교에서 자주 등장하는 균형점입니다.

시간 절약을 위해 메모리를 더 쓰는 경우
메모리 절약을 위해 연산 횟수를 늘리는 경우
이론상 좋은 복잡도지만 상수 비용이 커 실제로 느린 경우

그래서 복잡도 분석과 벤치마크는 함께 봐야 합니다.

복잡도 오판 반례와 복구 절차

다음 상황에서 복잡도 해석이 틀어지기 쉽습니다.

파이썬 리스트 insert를 O(1)로 오해함
해시 충돌 가능성을 완전히 무시함
재귀 깊이 한계를 고려하지 않음
평균 입력 분포만 보고 최악 입력을 배제함

복잡도 표기는 가정 위에서 성립하므로, 가정이 맞는지 반드시 확인해야 합니다.

로그 루프와 선형 루프 결합

문제 의도: 선형 루프와 로그 루프가 결합될 때 O(N log N)을 정확히 판별합니다.
입력 예시: N=8,16,32,64
출력 예시: 각 N에서 누적 연산 횟수 출력 안쪽 while이 몇 번 도는지만 세고, 바깥 반복 횟수와 곱하면 전체 비용을 구할 수 있습니다.

반복 구조가 섞일 때 복잡도를 잘못 읽는 경우가 많습니다.
아래 예제는 바깥 선형 루프와 안쪽 로그 루프가 결합된 전형적인 형태입니다.

main.cpp

#include <iostream>
#include <vector>
using namespace std;

int mixedCost(int n) {
    int ops = 0;
    for (int i = 0; i < n; ++i) {
        int step = 1;
        while (step < n) {
            ops++;
            step *= 2;
        }
    }
    return ops;
}

int main() {
    vector<int> sizes = {8, 16, 32, 64};
    for (int size : sizes) {
        cout << size << " " << mixedCost(size) << "\n";
    }
    return 0;
}

Main.java

public class Main {
    static int mixedCost(int n) {
        int ops = 0;
        for (int i = 0; i < n; i++) {
            int step = 1;
            while (step < n) {
                ops++;
                step *= 2;
            }
        }
        return ops;
    }

    public static void main(String[] args) {
        int[] sizes = {8, 16, 32, 64};
        for (int size : sizes) {
            System.out.println(size + " " + mixedCost(size));
        }
    }
}

main.py

def mixed_cost(n):
    ops = 0
    for _ in range(n):
        step = 1
        while step < n:
            ops += 1
            step *= 2
    return ops

for size in [8, 16, 32, 64]:
    print(size, mixed_cost(size))

main.rs

fn mixed_cost(n: i32) -> i32 {
    let mut ops = 0;
    for _ in 0..n {
        let mut step = 1;
        while step < n {
            ops += 1;
            step *= 2;
        }
    }
    ops
}

fn main() {
    for size in [8, 16, 32, 64] {
        println!("{} {}", size, mixed_cost(size));
    }
}