알고리즘의 성능 성적표
크리스가 시니어 개발자에게 코드 리뷰를 받고 있다.
자신 있게 제출한 이중 반복문 코드를 보며 시니어 개발자가 심각한 표정으로 말했다.
"크리스님, 이 로직은 시간 복잡도가 O(N^2)라서 데이터가 조금만 늘어나도 서버가 터질 것 같은데요? 최소한 O(N)이나 O(N log N)으로 줄여야 합니다."
크리스는 당황했다.
'오... 엔 제곱? 로그 엔? 수학 시간에 잤던 바로 그 로그(Log) 말인가?'
개발자들 사이에서 암호처럼 쓰이는 이 ”O”의 정체는 무엇일까? 오늘은 알고리즘의 효율성을 나타내는 만국 공용어, 빅오 표기법(Big-O Notation)을 완벽하게 이해해 보자.
1. 초시계 대신 '단계'를 센다
"이 코드가 얼마나 빠른가?"를 측정할 때, 우리는 흔히 시간(초)을 떠올린다.
"내 컴퓨터에서는 0.1초 걸렸어!"
하지만 이건 객관적인 지표가 될 수 없다. 슈퍼컴퓨터에서 돌린 0.1초와, 10년 된 노트북에서 돌린 0.1초는 다르기 때문이다. 그래서 컴퓨터 과학자들은 '시간(Seconds)' 대신 '연산 횟수(Steps)'를 세기로 약속했다.
2. 빅오(Big-O)의 세계: 빠름과 느림의 계급
빅오 표기법은 알고리즘의 성장 추세를 단순화해서 보여준다. 자주 쓰이는 4가지 계급만 알면 된다.
1계급: O(1) - 상수 시간 (Constant Time)
"데이터가 얼마나 많든 상관없어."
가장 이상적이고 빠른 속도다. 입력 데이터 $N$이 1개든 100만 개든 처리 속도가 똑같다.
2계급: O(log N) - 로그 시간 (Logarithmic Time)
"데이터가 2배 늘어나도, 할 일은 딱 한 단계만 늘어나."
$O(1)$ 다음으로 빠르다. 대량의 데이터를 처리할 때 매우 강력하다.
3계급: O(N) - 선형 시간 (Linear Time)
"데이터가 늘어나는 만큼 정직하게 시간이 걸려."
데이터가 10배 늘어나면 시간도 10배 걸린다. 우리가 짜는 대부분의 for 문이 여기에 해당한다.
4계급: O(N^2) - 이차 시간 (Quadratic Time)
"데이터가 10배 늘어나면, 시간은 100배 걸려." (위험 구간 🚨)
보통 이중 반복문(Nested Loop)을 쓸 때 발생한다. 데이터가 적을 땐 티가 안 나지만, 조금만 많아지면 성능이 지수적으로 나빠져서 서버를 다운시킨다.
3. 왜 '빅오(O)'인가? (최악의 시나리오)
"가끔은 운 좋게 한 번에 찾을 수도 있잖아요?"
맞다. 배열의 맨 앞에 찾는 값이 있다면 O(1) 만에 끝날 수도 있다. (이를 최선의 경우라고 한다.)
하지만 빅오 표기법은 항상 최악의 경우(Worst Case)를 기준으로 한다.
알고리즘의 성능을 보장하려면, "아무리 운이 나빠도 이 정도 시간 안에는 끝납니다"라는 상한선이 필요하기 때문이다.
그래서 우리는 "평균적으로 빠르다"보다는 "최악의 상황에서도 O(N)을 넘지 않는다"라고 말하는 것을 선호한다.
4. 자바스크립트 코드의 빅오 판별법
이제 크리스는 코드를 볼 때 머릿속으로 N을 대입해 본다.
// Case 1: 단순 반복
function printAll(arr) {
for (let i = 0; i < arr.length; i++) { // N번 반복
console.log(arr[i]);
}
}
// -> O(N)
// Case 2: 중첩 반복
function printPairs(arr) {
for (let i = 0; i < arr.length; i++) { // N번
for (let j = 0; j < arr.length; j++) { // N번
console.log(arr[i], arr[j]);
}
}
}
// -> N * N = O(N^2)
// Case 3: 반복문이 따로 있을 때
function doSomething(arr) {
for (let i = 0; i < arr.length; i++) {} // N번
for (let j = 0; j < arr.length; j++) {} // N번
}
// -> N + N = 2N. 하지만 상수는 무시한다. -> O(N)팁: 빅오 표기법에서는 상수를 무시한다. O(2N)이나 O(N + 100)이나, N이 무한대로 커지면 차이가 미미하기 때문에 그냥 O(N)으로 퉁친다. 중요한 건 기울기(추세)다.
핵심 정리
시간(Time)에 대한 개념을 잡았다. 그런데 알고리즘에는 시간만큼 중요한 자원이 하나 더 있다. 바로 공간(Space), 즉 메모리다.
엄청나게 빠르지만 램(RAM)을 100GB나 차지하는 코드는 좋은 코드일까?
다음 글, "공간 복잡도: 속도만큼 중요한 메모리 이야기"에서 계속된다.