왜 복잡도를 배워야 하는가

01편에서 “같은 리스트 ADT라도 배열로 구현하느냐 연결리스트로 구현하느냐에 따라 속도가 달라진다”고 했다. 그런데 “속도가 다르다”는 말은 너무 막연하다. 1초 걸리던 것이 0.9초로 줄었다는 뜻인지, 데이터가 두 배로 늘어났을 때 처리 시간도 두 배로 늘어난다는 뜻인지, 아니면 네 배로 늘어난다는 뜻인지 구분하지 못하면 자료구조를 비교할 수 없다.

복잡도(complexity)는 이 질문에 답하기 위한 도구다. 입력의 크기 n이 커질 때 실행 시간(시간복잡도)이나 사용하는 메모리(공간복잡도)가 어떤 비율로 늘어나는지를 수식으로 나타낸 것이다. 중요한 것은 복잡도가 “정확히 몇 초 걸리는가”를 재는 도구가 아니라는 점이다. 컴퓨터 성능, 프로그래밍 언어, 컴파일러 최적화에 따라 실제 걸리는 시간은 다 다르다. 복잡도는 그런 환경 차이를 걷어내고 “데이터가 늘어날 때 연산 횟수가 늘어나는 추세”만 뽑아서 비교하는 도구다.

쉽게 말하면: 복잡도는 “몇 초 걸리는가”가 아니라 “데이터가 두 배, 열 배로 늘어나면 일이 몇 배로 늘어나는가”를 재는 잣대다.

최선·평균·최악 — 같은 알고리즘도 입력에 따라 다르다

같은 알고리즘이라도 어떤 데이터가 들어오느냐에 따라 걸리는 시간이 달라질 수 있다. 이 차이를 구분하는 세 가지 시나리오가 있다.

• 최선의 경우(best case): 가장 운이 좋은 입력이 들어왔을 때. 연산 횟수가 가장 적다.
• 평균의 경우(average case): 있을 수 있는 모든 입력을 확률적으로 고려했을 때 기대되는 연산 횟수.
• 최악의 경우(worst case): 가장 운이 나쁜 입력이 들어왔을 때. 연산 횟수가 가장 많다.

순차 탐색(linear search, 배열의 맨 앞부터 하나씩 확인하며 원하는 값을 찾는 방법)을 예로 직접 세어 보자. 크기 n인 배열에서 특정 값을 찾는다고 하면 다음과 같다.

평균의 경우를 직접 유도해 보면, 값이 인덱스 0에 있을 확률도 1/n, 인덱스 1에 있을 확률도 1/n, …, 인덱스 n-1에 있을 확률도 1/n이라고 가정할 때 기대 비교 횟수는 각 위치까지 가는 데 필요한 비교 횟수(1, 2, 3, …, n)를 전부 더해 n으로 나눈 값이다.

(n+1)/2는 결국 n이 커질수록 n/2에 가까워지므로, “평균적으로 절반쯤 확인한다”는 직관과 맞아떨어진다.

자주 틀리는 점: 시험 문제에서 “이 알고리즘의 복잡도는 O(n)이다”라고만 쓰여 있으면 보통 최악의 경우를 기준으로 한 것이다. 최선의 경우 O(1)이 가능하다고 해서 전체 복잡도가 O(1)이라고 답하면 틀린다. 복잡도를 이야기할 때는 항상 “어떤 경우의 복잡도인가”를 먼저 확인하는 습관을 들여야 한다.

Big-O 표기법 — 반복 횟수를 직접 세어 유도하기

Big-O 표기법(Big-O notation, 대문자 O로 쓰고 “빅오”라고 읽는다)은 입력 크기 n이 커질 때 연산 횟수가 늘어나는 속도의 상한(upper bound, “많아야 이 정도 속도로 늘어난다”는 뜻)을 나타내는 표기법이다. 정의를 외우기보다, 실제 코드의 반복 횟수를 세어서 Big-O를 유도하는 절차를 몸에 익히는 것이 시험에 훨씬 유리하다.

예시 1 — 단순 반복문

배열 크기가 n일 때, 배열의 모든 원소를 한 번씩 출력하는 반복문을 생각해 보자(의사코드).

for i = 0 to n-1:
    print(array[i])

이 반복문은 i가 0부터 n-1까지 움직이므로 총 n번 실행된다. 반복 횟수가 n에 정비례하므로 이 코드의 시간복잡도는 O(n)이다.

예시 2 — 중첩 반복문(선택 정렬의 비교 횟수)

선택 정렬(selection sort, 16편에서 자세히 다룬다)은 매 단계마다 아직 정렬되지 않은 부분에서 가장 작은 값을 찾아 앞으로 옮기는 정렬 방법이다. 의사코드는 다음과 같다.

for i = 0 to n-2:
    가장 작은 값의 위치 찾기:
        for j = i+1 to n-1:
            array[j]와 비교

바깥 반복문 i가 한 번 돌 때마다 안쪽 반복문이 몇 번 도는지 직접 세어 보자.

전체 비교 횟수는 이 값들을 모두 더한 것이다.

n = 5인 구체적인 배열로 검산해 보면 4 + 3 + 2 + 1 = 10이고, 공식으로 계산해도 5 × 4 / 2 = 10으로 정확히 일치한다.

n(n-1)/2를 전개하면 다음과 같다.

Big-O를 구할 때는 이 식에서 가장 빠르게 커지는 항(최고차항)만 남기고, 그 항에 곱해진 상수도 지운다. (n^2 - n)/2에서 n이 커질수록 n^2이 n보다 압도적으로 커지므로 -n은 무시하고, 1/2이라는 상수 배율도 지운다. 그렇게 남는 것이 n^2이므로 선택 정렬의 비교 횟수는 O(n^2)이다.

왜 상수와 낮은 차수 항을 지우는가: n이 100만 정도로 커지면 n^2/2와 n^2의 차이(2배)는 n^2과 n의 차이(100만 배)에 비하면 무시할 수 있을 만큼 작다. Big-O는 “n이 아주 커졌을 때 무엇이 성장 속도를 지배하는가”만 보는 도구이므로, 상수 배율이나 낮은 차수 항은 그 지배력에 영향을 주지 못해 생략한다.

예시 3 — 상수 시간 연산

배열에서 인덱스로 원소 하나를 바로 꺼내는 연산(array[3]처럼)은 n이 아무리 커져도 딱 한 번의 주소 계산과 한 번의 메모리 접근만 하면 된다(주소 계산 방식은 03편에서 자세히 다룬다). 이렇게 입력 크기와 무관하게 항상 일정한 횟수만 실행되는 연산은 O(1)로 표기하며, “상수 시간”이라고 부른다.

Big-Theta 표기법 — 상한과 하한이 만나는 지점

Big-O가 “많아야 이만큼”이라는 상한만 말해 준다면, 반대로 “적어도 이만큼은 걸린다”는 하한을 나타내는 표기법도 있다. 이것을 Big-Omega 표기법(Big-Ω notation, 그리스 문자 오메가를 써서 나타낸다)이라고 부른다. 예를 들어 순차 탐색은 운이 아주 좋으면 1번 만에 끝날 수 있으므로(최선의 경우) 하한은 Ω(1)이라고 말할 수 있다.

Big-Theta 표기법(Big-Θ notation, 그리스 문자 세타를 써서 나타내고 “빅세타”라고 읽는다)은 상한(O)과 하한(Ω)이 같은 차수로 딱 맞아떨어질 때 사용하는 표기법이다. 즉 “최선의 경우든 최악의 경우든 결국 같은 차수로 늘어난다”는 뜻이며, 그 알고리즘(또는 특정 상황에서의 알고리즘 동작)을 가장 정확하게 나타내는 표기법이다.

선택 정렬의 비교 횟수를 다시 생각해 보자. 앞서 유도한 n(n-1)/2라는 식은 배열에 들어 있는 값이 무엇이든, 이미 정렬돼 있든 아니든 항상 똑같이 계산된다(선택 정렬은 값을 비교할 때 “더 작은 값을 찾기 위해” 무조건 남은 원소를 전부 훑어보기 때문이다). 즉 최선의 경우와 최악의 경우가 똑같이 n(n-1)/2이므로, 선택 정렬의 비교 횟수는 상한도 O(n²)이고 하한도 Ω(n²)이라서 두 표기가 정확히 만난다. 이럴 때 Θ(n²)이라고 쓴다.

반면 순차 탐색은 최선이 O(1)이고 최악이 O(n)으로 차수 자체가 다르므로, 순차 탐색 전체를 하나의 Θ로 묶어 말할 수 없다. 다만 “순차 탐색의 최악의 경우”만 떼어놓고 보면 그 경우는 항상 정확히 n번 비교하므로 그 상황에 한해서는 Θ(n)이라고 말할 수 있다.

쉽게 말하면: O는 “최대 이 정도”라는 약속, Ω는 “최소 이 정도”라는 약속, Θ는 그 둘이 똑같아서 “정확히 이 정도 속도로 늘어난다”고 자신 있게 말할 수 있는 경우다.

자주 틀리는 점: 실무나 시험 문제에서는 관습적으로 최악의 경우 상한을 나타내는 O 표기만 쓰고 넘어가는 경우가 많다. 그래서 “이 정렬의 시간복잡도는 O(n log n)이다”라는 문장을 “최악의 경우에도 O(n log n)을 넘지 않는다”는 뜻으로 편하게 쓰는 관행이 있다. 하지만 O와 Θ의 정의 차이를 묻는 문제에서는 “O는 상한만 보장하고, Θ는 상한과 하한이 모두 그 차수로 일치함을 보장한다”는 정의 차이를 정확히 짚어야 한다.

자주 등장하는 복잡도 차수와 실제 규모 감각

시험에 자주 나오는 차수를 성장 속도가 느린 순서대로 나열하면 다음과 같다.

이 표에서 눈여겨볼 부분은 n이 10에서 1,000으로 100배 늘어날 때, O(n)은 그대로 100배(10 → 1,000)로 늘어나지만 O(n²)은 100배의 제곱인 10,000배(100 → 1,000,000)로 늘어난다는 점이다. 데이터가 커질수록 O(n)과 O(n²)의 차이는 상상 이상으로 벌어진다. 이것이 “같은 문제를 O(n²) 알고리즘이 아니라 O(n log n) 알고리즘으로 풀어야 하는 이유”의 근거가 된다.

공간복잡도 — 메모리도 같은 방식으로 잰다

공간복잡도(space complexity)는 시간 대신 메모리 사용량이 입력 크기 n에 따라 어떻게 늘어나는지를 같은 O 표기법으로 나타낸 것이다. 예를 들어 배열을 한 번 훑으며 합계를 구하는 코드는 n개의 원소를 담을 배열(입력 자체)을 빼면 합계를 저장할 변수 하나만 더 쓰므로 추가로 사용하는 공간은 O(1)이다. 반면 입력 배열을 정렬한 결과를 새 배열에 복사해서 담는 방식이라면 크기 n짜리 배열을 하나 더 만들어야 하므로 O(n)이다.

자주 틀리는 점: 공간복잡도를 계산할 때 “입력 자체가 차지하는 메모리”까지 포함할지, “입력을 제외하고 추가로 쓰는 메모리”만 셀지는 문제에서 요구하는 기준에 따라 다르다. 흔히 “추가 공간”만 묻는 경우를 O(1) 추가 공간(in-place, 제자리 처리라고 부른다. 16편의 정렬 알고리즘 비교표에서 이 개념이 다시 나온다)이라고 부르므로, 문제에서 “제자리(in-place)“라는 표현이 나오면 입력 자체의 크기는 세지 않는다는 뜻으로 읽어야 한다.

자주 틀리는 점

• 최선의 경우를 전체 복잡도로 착각하는 실수: 별도 언급이 없으면 시험에서 묻는 복잡도는 대개 최악의 경우다.
• 상수를 살려서 계산하는 실수: O(3n + 5)처럼 상수를 남겨 쓰면 틀린다. 반드시 O(n)으로 정리해서 답해야 한다.
• 낮은 차수 항을 지우지 않는 실수: O(n^2 + n)이 아니라 O(n^2)이 옳다. 두 항이 있으면 가장 큰 차수만 남긴다.
• Big-O와 Big-Theta를 같은 말로 쓰는 실수: O는 상한만 보장하고, Θ는 상한과 하한이 같은 차수로 일치한다는 더 강한 보장이다. “이 알고리즘은 O(n)이다”라는 말이 “Θ(n)이다”라는 말과 항상 같지는 않다.
• 복잡도를 실제 실행 시간(초)과 혼동하는 실수: 복잡도는 입력이 커질 때의 증가 추세를 나타낼 뿐, 특정 컴퓨터에서 몇 초 걸리는지를 말해주지 않는다.

핵심 정리

• 최선·평균·최악은 “어떤 입력이 들어왔을 때인가”를 구분하는 기준이며, 시험에서 복잡도만 묻는 문제는 보통 최악의 경우를 가리킨다.
• Big-O는 반복문의 실행 횟수를 직접 세어 식을 세운 뒤, 최고차항만 남기고 상수를 지워서 유도한다.
• Big-Omega는 하한, Big-Theta는 상한과 하한이 같은 차수로 일치할 때 쓰는 표기법이다.
• 자주 나오는 차수는 O(1) → O(log n) → O(n) → O(n log n) → O(n^2) → O(2^n) 순으로 성장 속도가 빨라진다.
• 공간복잡도는 메모리 사용량을 같은 방식으로 표기하며, “제자리(in-place)“는 추가 공간 O(1)을 뜻한다.

마무리 복습

참고 자료

• 국가평생교육진흥원 과목별 평가영역  — 자료구조 과목의 평가영역과 출제 범위를 확인해 복잡도 개념의 시험 비중을 맞추는 데 참고했다.
• Big-O Cheat Sheet  — 자료구조·정렬 알고리즘별 시간·공간 복잡도를 한눈에 비교할 수 있는 공개 참고 자료.