알고리즘 문제를 풀다 보면 "이 코드는 시간 초과 나겠는데?" 혹은 "이 정도면 통과하겠다"는 감을 잡아야 할 때가 많습니다. 이 감을 수치화한 것이 바로 시간 복잡도(Time Complexity)이고, 이를 표현하는 대표적인 방법이 빅오 표기법(Big-O Notation) 입니다.
이번 글에서는 빅오 표기법이 왜 필요한지, 어떻게 계산하는지, 그리고 실전 코딩 테스트에서 어떻게 활용하는지까지 예시 코드와 함께 차근차근 정리해보겠습니다.
1. 연산 횟수부터 시작하기
다음과 같은 함수가 있다고 가정해봅시다.
public class SolutionExample {
public static int solution(int n) {
int count = 0;
// 구간 1: n번 반복 (n번 증가 연산)
for (int i = 0; i < n; i++) {
count++;
}
// 구간 2: n * n번 반복 (n^2번 증가 연산)
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
count++;
}
}
// 구간 3: 2n번 반복 (2n번 증가 연산)
for (int i = 0; i < 2 * n; i++) {
count++;
}
// 구간 4: 상수 횟수 (5번 증가 연산)
for (int i = 0; i < 5; i++) {
count++;
}
return count;
}
public static void main(String[] args) {
System.out.println(solution(6)); // 6^2 + 6 + 2*6 + 5 = 59
}
}solution() 함수는 주석 영역별로 각각 n², n, 2n, 5번의 증가 연산을 하며, 결괏값은 곧 연산 횟수를 의미합니다. solution(6)을 호출하면 6² + 6 + 2×6 + 5, 즉 연산 횟수는 59입니다.
이때 solution() 함수의 연산 횟수는 식으로 다음과 같이 표현할 수 있습니다.
n = x일 때, f(x) = x² + 3x + 5
2. 빅오 표기법이란?
f(x)는 정확한 연산 횟수를 나타내는 식이지만, 알고리즘 성능을 이야기할 때 이 정확한 값 자체는 큰 의미가 없습니다. x가 아주 커지면 3x + 5 같은 항은 x²에 비해 무시할 수 있을 만큼 작아지기 때문입니다.
그래서 f(x)를 있는 그대로 쓰지 않고, f(x)의 증가 속도를 대표하는 더 단순한 함수 g(x)로 뭉뚱그려 표현합니다. 이때 다음 조건을 만족하는 g(x)가 있다면, f(x)의 최악의 시간 복잡도는 O(g(x)) 라고 씁니다.
- 특정 x 시점 이후부터 항상 f(x) ≤ C × g(x)를 만족
- C는 상수
쉽게 말해 g(x)에 상수 C를 곱했을 때, 특정 시점부터 f(x)를 넘어서는지 여부를 보면 됩니다. f(x) = x² + 3x + 5의 경우, C = 2, g(x) = x²으로 잡으면 됩니다. 그래프로 보면 금방 이해할 수 있습니다.
- 처음에는(x가 작을 때) f(x) = x² + 3x + 5 (회색)가 2x² (파란색)보다 위에 있습니다.
- 하지만 x가 어느 지점을 넘어서면 2x²이 f(x)를 완전히 추월해서, 그 뒤로는 계속 위에 있습니다.
이게 바로 "특정 x 시점 이후부터 항상 f(x) ≤ C·g(x)"가 성립하는 모습이고, 그래서 f(x)의 시간복잡도는 O(x²) 이라고 쓸 수 있는 것입니다.
다항함수 vs 지수함수 vs 로그함수
- 다항함수: x가 밑(base), 지수는 고정 (x², x⁵ 등) → x² , 3x²
- 지수함수: x가 지수(exponent), 밑은 고정 (2ˣ, 10ˣ 등) → 2ˣ
- 로그함수: log x → 증가 속도가 매우 느림
| 수식 | 빅오 표기 | 설명 |
|---|---|---|
| 3x² + 5x + 6 | O(x²) | 다항함수로 구성되어 있으므로 최고차항 x²만 남습니다. |
| x + log x | O(x) | 다항함수와 로그함수로 구성되어 있으므로, 증가폭이 더 낮은 로그함수는 사라지고 다항함수만 남습니다. |
| 2ˣ + 10x⁵ + 5x² | O(2ˣ) | 지수함수는 다항함수보다 빠르게 증가하므로 지수함수만 남습니다. |
| 5x² - 6x | O(x²) | 최고차항 x²만 남습니다. |
간단히 실제 숫자로 지수함수와 다항함수의 증가 속도 차이를 비교해보면 다음과 같습니다.
| x | 2ˣ | 10x⁵ |
|---|---|---|
| 10 | 1,024 | 1,000,000 |
| 30 | 약 10억 | 약 2.4억 |
| 100 | 약 1.27×10³⁰ | 약 1×10¹⁰ |
x가 작을 때는 다항함수(10x⁵)가 더 커 보이지만, x = 30 근처를 기점으로 지수함수(2ˣ)가 다항함수를 완전히 추월하고, 그 뒤로는 격차가 계속 벌어지기만 합니다. 그래서 지수함수와 다항함수가 함께 있으면 다항함수는 아무리 차수가 높아도 결국 지수함수에 묻혀버립니다.
3. 최고차항만 남기는 우선순위
여러 종류의 함수가 섞여 있을 때는 아래 우선순위를 기준으로, 증가 속도가 가장 빠른 함수 하나만 남기고 나머지는 지웁니다.
| 함수 종류 | 예 |
|---|---|
| 지수함수 | 2ˣ |
| 다항함수 | 3x² |
| 로그함수 | log x |
이 우선순위대로면, 다항함수와 로그함수가 섞여 있을 때는 로그함수를, 지수함수와 다항함수가 섞여 있다면 다항함수를 지워야 합니다.
그래프에 등장하는 함수들을 증가 속도가 느린 것부터 빠른 순서로 나열하면 다음과 같습니다.
- log x — 가장 느림
- x
- x log x
- x²
- 2ˣ — 지수함수
- x! — 팩토리얼, 가장 빠름
x가 작을 땐 x!, 2ˣ, x²가 비슷하게 붙어 있다가, x가 커질수록 순서대로 벌어지면서 x! > 2ˣ > x² 순으로 위로 솟구치는 것을 볼 수 있습니다.
4. 코딩 테스트에 시간 복잡도 활용하기
빅오 표기법을 알았다면, 이를 코딩 테스트에 어떻게 활용할까요? 코딩 테스트 문제에는 제한 시간이 있으므로, 문제를 분석한 후 빅오 표기법을 활용해서 해당 알고리즘을 적용했을 때 제한 시간 내에 출력값이 나올 수 있을지 확인해볼 수 있습니다. 이를 통해 문제 조건에 맞지 않는 알고리즘을 적용하느라 낭비하는 시간을 줄일 수 있습니다.
일반적으로 다음을 기준으로 알고리즘을 선택합니다.
"컴퓨터가 초당 연산할 수 있는 최대 횟수는 1억 번이다."
다만 이 1억 번은 어디까지나 이론적인 최대치입니다. 실제 코드에는 배열 접근, 함수 호출, 조건 분기 등 단순 연산보다 무거운 작업이 섞여 있고, 언어나 실행 환경에 따라서도 속도 차이가 크게 납니다. 그래서 1억 번을 그대로 믿고 알고리즘을 짜면 시간 초과가 날 위험이 있습니다.
또한 코딩 테스트 문제는 출제자가 의도한 로직을 구현했다면 대부분의 코드가 정답 처리될 수 있도록, 채점 시간을 충분히 여유 있게 지정합니다. 따라서 실전에서는 연산 횟수를 1,000만 ~ 3,000만 정도로 보수적으로 잡아서 시간 복잡도를 생각하면 됩니다.
예를 들어 제한 시간이 1초인 문제에 연산 횟수가 3,000만이 넘는 알고리즘은 사용하면 안 됩니다. 이 기준으로 제한 시간이 1초인 문제에 각 시간복잡도별로 허용할 수 있는 N의 가용 범위를 가늠해볼 수 있습니다.
5. 실전 예제: 별찍기로 시간 복잡도 구해보기
아래와 같이 별을 계단 모양으로 찍는 코드가 있다고 가정해봅시다.
public class StarPattern {
public static void printStars(int n) {
int count = 0; // 연산 횟수(별 찍는 횟수) 카운트
for (int i = 1; i <= n; i++) {
StringBuilder sb = new StringBuilder();
for (int j = 1; j <= i; j++) {
sb.append("*");
count++; // 별 하나 찍을 때마다 연산 1회
}
System.out.println(sb);
}
System.out.println("총 연산 횟수: " + count);
}
public static void main(String[] args) {
int n = 5;
printStars(n);
// 1 + 2 + 3 + 4 + 5 = 15 = 5*(5+1)/2
}
}실행 결과는 다음과 같습니다.
*
**
***
****
*****
총 연산 횟수: 15각 줄마다 별을 하나씩 찍는 게 연산 1회라고 하면, i번째 줄에서는 별을 i번 찍으므로 전체 연산 횟수는 다음과 같습니다.
왜 N(N+1)/2가 될까?
같은 수열을 정순, 역순으로 나란히 써서 더해보면 규칙이 보입니다. 이 방법은 수학자 가우스(Carl Friedrich Gauss)가 어린 시절 1부터 100까지의 합을 순식간에 구했다는 일화로 유명해서, 흔히 가우스 합(Gauss's sum) 또는 가우스 덧셈법이라고 부릅니다.
1 + 2 + 3 + ... + (N-1) + N
N + (N-1) + (N-2) + ... + 2 + 1
------------------------------------------
(N+1)+ (N+1)+ (N+1)+ ... + (N+1)+ (N+1)세로로 더한 값이 전부 (N+1)로 동일하고, 이런 쌍이 N개 있으므로
2S = N × (N+1) → S = N(N+1) / 2이를 전개하면 다음과 같습니다.
N(N+1) / 2 = (1/2)N² + (1/2)N여기서 최고차항만 남기는 규칙을 적용하면 ½N과 상수 ½은 지워지고 N²만 남습니다. 따라서 별찍기의 시간복잡도는 O(N²) 입니다.
실제로 N = 5일 때 위 자바 코드를 실행하면 1+2+3+4+5 = 15이고, 공식으로 계산해도 5×(5+1)/2 = 15로 정확히 일치하는 것을 확인할 수 있습니다.
마무리
정리하면, 빅오 표기법은 알고리즘의 정확한 연산 횟수가 아니라 입력이 커질 때 얼마나 빠르게 증가하는가에 초점을 맞춘 표기법입니다.
- 함수를 이루는 항들을 나열한다.
- 지수함수 > 다항함수 > 로그함수 순으로, 가장 빠르게 증가하는 종류 하나만 남긴다.
- 남은 함수 중에서도 최고차항만 남긴다.
- 이렇게 구한 시간복잡도를 문제의 제한 시간(연산 횟수 1,000만~3,000만 기준)과 비교해, 적절한 알고리즘인지 미리 가늠한다.
이 흐름만 기억해두면, 문제를 보자마자 "이 알고리즘으로 풀면 통과할 수 있겠다 / 없겠다"를 훨씬 빠르게 판단할 수 있습니다.