시간 복잡도와 공간 복잡도

시간 복잡도(time complexity)는 입력이 커질 때 알고리즘의 실행 시간이 얼마나 빨리 늘어나는지를 나타낸다. 공간 복잡도(space complexity)는 같은 방식으로 메모리 사용량이 늘어나는 정도를 나타내며, 둘 다 빅오 표기법(Big-O notation)으로 입력 크기를 n이라 두고 O(n)처럼 적는다. 이 문서는 자료구조(data structure)의 연산 비용을 비교하는 공통 언어인 빅오 표기법을 적는 법과 대표 복잡도 사이의 크기 차이를 다룬다.

왜 초가 아니라 증가율로 보는가

같은 코드라도 실행 시간(초)은 CPU 성능, 언어, 컴파일러(compiler), 그날의 입력에 따라 달라진다. 그래서 "0.3초 걸렸다"는 숫자로는 두 알고리즘을 공정하게 비교할 수 없다. 대신 "입력 크기 n이 10배가 되면 비용이 몇 배가 되는가"를 보면 기계와 상관없는 알고리즘 자체의 성질을 비교할 수 있다. 입력이 작을 때는 어느 쪽이든 빠르므로, 차이가 드러나는 큰 입력에서의 증가율이 실제로 중요하다.

빅오 표기법

빅오 표기법은 비교·대입·덧셈처럼 입력 크기와 상관없이 일정한 시간이 드는 단순 연산을 하나로 세고, 그 횟수를 n에 대한 식으로 세운 뒤, 가장 빨리 커지는 항만 남기고 상수 계수를 버린다. 예를 들어 연산 횟수가 3n² + 5n + 100이면 O(n²)이라 쓴다. n이 백만이면 3n²은 3조이고 5n은 5백만이라, 작은 항은 전체에 거의 영향을 주지 않는다. 상수 3을 버리는 이유는 그 값이 기계와 구현에 따라 바뀌는 부분이라 알고리즘의 성질이 아니기 때문이다.

엄밀히 말하면 빅오는 상한이다. 비교 기준이 될 함수를 g(n)이라 하자(예: g(n) = n²). 어떤 상수 c가 있어서 충분히 큰 n에서 비용이 늘 c × g(n) 이하이면 O(g(n))이라 쓴다. 그래서 O(n)인 알고리즘을 O(n²)이라 적어도 틀리지는 않지만, 보통은 가장 딱 맞는 상한을 말한다.

// 중복 찾기: 바깥 반복 n번 × 안쪽 반복 최대 n번 → O(n²)
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        if (a[i] == a[j]) return true;
return false;

대표 복잡도 비교

아래 표의 "연산 수"는 n = 10⁶(백만)일 때 대략의 횟수다. 이진 탐색(binary search)은 정렬된 데이터에서 가운데 값과 비교해 범위를 절반씩 줄이는 탐색이라, 백만 개에서도 약 20번 만에 끝난다. log n(밑이 2인 로그)은 n을 몇 번 반으로 나눠야 1이 되는지를 뜻하므로, 백만(≈ 2²⁰)이면 약 20이다. 배열(array)은 칸이 메모리에 연속으로 붙어 있어 칸 번호(인덱스, index)만 알면 바로 칸을 찾는 자료구조다.

표기	이름	예	n = 10⁶일 때 연산 수
O(1)	상수	배열 인덱스로 읽기	1
O(log n)	로그	이진 탐색	약 20
O(n)	선형	배열 한 번 훑기	10⁶
O(n log n)	선형 로그	병합 정렬(merge sort)	약 2 × 10⁷
O(n²)	이차	모든 쌍 비교	10¹²
O(2ⁿ)	지수	모든 부분집합 나열	사실상 계산 불가

모든 부분집합을 나열하면 원소마다 넣는다·뺀다 두 가지를 고르므로 부분집합이 2ⁿ개가 되어, n이 하나 늘 때마다 할 일이 두 배가 된다. n이 작을 때부터 벌어지기 시작하는 모습을 그림으로 보면 차이가 더 분명하다. 아래 그림에서 빨강은 n², 주황은 n log n, 파랑은 n이다.

다이어그램 로딩…

감을 잡으려고 단순 연산을 1초에 10⁸번 한다고 가정하면, O(n log n)은 0.2초 안팎이지만 O(n²)은 10⁴초, 즉 약 3시간이 걸린다. 그래서 입력이 크면 O(n²)을 O(n log n)으로 줄이는 것이 어떤 코드 최적화보다 효과가 크다.

이어지는 내용은 시간 복잡도와 공간 복잡도 2에서 다룬다.

면접 포인트

• "빅오 표기법이 뭔가요?" → 입력이 커질 때 비용 증가율의 상한. 가장 큰 항만 남기고 상수 무시.
• "왜 상수를 무시하나요?" → 상수는 기계·구현에 따라 바뀌고, n이 커지면 증가율 차이가 압도한다. 단 실제 성능 비교에서는 상수도 중요할 수 있다.
• "대표 복잡도의 크기 순서는?" → O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ) 순으로 커진다. n이 크면 한 단계 낮추는 것이 어떤 코드 최적화보다 효과가 크다.