알고리즘 복잡도와 O-Notation

왜 배우는가: 알고리즘 복잡도는 입력 크기가 커질 때 시간과 메모리가 얼마나 늘어나는지를 판단하는 기본 기준이다. 실무에서는 데이터가 커졌을 때 시스템이 버틸지를 예측하는 데 쓰이고, 시험에서는 O-Notation의 정의와 유형별 연산시간 차이를 묻는 문제로 반복해 나온다.

출제 이력: 제134회 3교시 4번, 제89회 4교시 1번

1. 한 줄 정의와 핵심 키워드

알고리즘 복잡도는 입력 크기 n이 증가할 때 알고리즘이 필요로 하는 시간과 메모리의 증가 추이를 점근 표기법으로 나타낸 것이다.

• 시간 복잡도(Time Complexity)
• 공간 복잡도(Space Complexity)
• 점근 표기법(Asymptotic Notation)
• 빅오 표기법(Big-O)
• 최악 경우(Worst Case)
• 입력 크기(Input Size, n)
• 최고차항(Dominant Term)
• 상수 인자(Constant Factor)

2. 개념 풀이

쉽게 말하면 데이터가 10배 늘면 프로그램이 몇 배 느려지는지를 셈하는 방법이다. 같은 일을 하는 두 알고리즘이라도 데이터가 적을 때는 차이가 작지만, 데이터가 커지면 복잡도 차이가 실행 시간 차이로 크게 드러난다. 그래서 정확한 초 단위 시간 대신 입력 크기에 따른 증가 모양을 본다.

복잡도 분석은 알고리즘이 수행하는 기본 연산 횟수를 입력 크기 n의 함수 T(n)으로 세우는 것에서 시작한다. 이 함수에서 최고차항만 남기고 계수와 낮은 차수의 항은 버리는 방식으로 점근적 성장률을 표기한다. 예를 들어 T(n)=5n³+3n이면 최고차항 n³만 남겨 O(n³)으로 쓴다.

시간 복잡도는 기본 연산 횟수가 입력 크기에 따라 얼마나 늘어나는지를 나타낸다. 공간 복잡도는 알고리즘이 실행을 끝낼 때까지 필요한 메모리의 양을 나타내며, 입력이 차지하는 공간과 실행 중 쓰는 보조 공간을 합하여 본다.

분석 대상은 같은 크기의 입력이라도 값에 따라 실행 시간이 달라지므로 보통 세 가지 경우로 나눈다. 최악 경우(Worst Case)는 가장 오래 걸리는 입력에 대한 상한이고, 평균 경우(Average Case)는 입력 분포를 가정한 기댓값이며, 최선 경우(Best Case)는 가장 빠른 입력에 대한 하한이다. 시험 답안에서는 특별한 언급이 없으면 최악 경우를 기준으로 한다.

최악 경우 상한을 O로 표기하고 최선 경우 하한을 Ω로 표기하며, 두 값이 같을 때 Θ로 표기한다. 이 세 기호가 O-Notation의 유형이다.

3. 등장 배경과 필요성

초기 컴퓨터에서는 프로그램 실행 시간을 실제로 재어 성능을 비교했다. 그러나 같은 알고리즘도 하드웨어, 컴파일러, 입력 데이터에 따라 측정값이 달라 공정한 비교가 어려웠다. 그래서 특정 기계에 의존하지 않고 입력 크기에 따른 증가율만으로 알고리즘을 비교할 필요가 생겼다.

데이터 양이 기하급수적으로 늘어나면서 이 필요는 더 커졌다. 수백만 건의 데이터에서 n² 알고리즘은 실용적이지 않지만 n log n 알고리즘은 처리할 수 있다. 이런 차이를 하드웨어를 바꾸기 전에 설계 단계에서 판단하려면 점근 표기법이 필요하다.

또한 빅오 표기법은 수학자 바흐만과 란다우가 정리한 표기법에서 출발했다. 컴퓨터 과학에서는 이를 입력 크기에 따른 실행 시간과 공간 요구량을 분류하는 도구로 가져다 쓴다.

4. 구성요소·원리·절차

알고리즘 복잡도는 입력 크기 n에 대한 시간 복잡도와 공간 복잡도로 나타낸다. 시간 복잡도는 기본 연산 횟수 T(n), 공간 복잡도는 메모리 사용량 S(n)을 뜻한다. 두 함수는 정확히 세우기 어려우므로 최고차항만 남기는 점근 표기로 단순화한다. 핵심은 입력 크기 n이 충분히 커질 때의 증가 경향을 보는 것이다.

표의 구성요소 중 T(n)과 S(n)이 분석의 대상이다. 입력 공간은 입력 자체가 차지하는 메모리이고, 보조 공간은 실행 중 추가로 쓰는 메모리다. 공간 복잡도는 보통 보조 공간을 기준으로 따진다.

원리는 세 가지다. 첫째, 기본 연산 한 번이 고정 시간이면 실행 시간은 T(n)에 상수배로 비례한다. 따라서 상수 인자는 무시한다. 둘째, 같은 크기의 입력이라도 실행 시간이 달라지므로 최선·평균·최악 경우를 나눠 분석한다. 셋째, n이 커지면 낮은 차수항의 기여가 작아지므로 최고차항만 남긴다.

예를 들어 T(n)=5n³+3n이면 최고차항은 5n³이다. 계수 5를 제거하면 점근적 시간 복잡도는 O(n³)이다. n=100이면 5n³은 5,000,000이고 3n은 300이므로 3n 항은 무시해도 된다.

$f(n)=O(g(n)) \Leftrightarrow ∃\,c>0,\; n_0 :\; f(n) ≤ c·g(n)\ (n ≥ n_0)$

여기서 f(n)은 실제 연산 횟수, g(n)은 비교 함수, c는 상수 배수, n₀은 상한이 성립하기 시작하는 입력 크기다.

시간 복잡도 도출 절차는 다음과 같다.

• 알고리즘을 기본 연산 단위로 분해한다.
• 입력 크기 n에 대해 연산 횟수 T(n)을 세운다. 반복문은 합으로, 재귀는 점화식으로 표현한다.
• T(n)에서 최고차항만 남긴다.
• 최고차항의 계수와 상수를 제거한다.
• 최악·평균·최선 중 목적에 맞는 경우를 고르고, O, Ω, Θ 중 적합한 표기를 정한다.
• 공간 복잡도는 S(n)을 같은 방식으로 구한다.

5. 관련 법령·기준·표준

이 개념은 법령이나 고시가 아니라 계산 이론의 점근 표기 규칙이 기준이다. 세 표기의 경계 조건은 아래와 같다.

Big-O는 함수의 성장률에 대한 상한만 준다. Big-Ω는 하한을 주고, 최선 경우 분석에 주로 쓰인다. Big-Θ는 상한과 하한이 같을 때만 쓸 수 있으므로 가장 정확하지만 증명이 더 어렵다.

대표 등급별 수행 횟수 기준은 다음과 같다.

공간 복잡도도 같은 점근 표기로 쓴다. 입력 공간과 보조 공간을 합산하며, 보조 공간만 쓰는 경우가 많다.

6. 유형과 비교

알고리즘 복잡도는 표기법(점근 기호)과 분석 경우(최악·평균·최선)를 함께 봐야 정확히 표현된다. 먼저 점근 표기법 세 가지를 비교한다.

표 아래 설명: Big-O는 최악 경우의 보장으로 설계 검토에서 가장 많이 쓴다. Big-Θ는 상한과 하한이 일치할 때만 쓸 수 있어 엄밀하지만, 평균 분석과 정확한 증가율 산정이 어렵다.

다음은 증가율 유형별 연산 횟수의 차이다. 입력 크기 n이 10과 1,000일 때 기본 연算 횟수를 비교한다.