프로그래밍을 독학하거나 실무에서 개발을 하다 보면, 기능은 완벽하게 동작하는데 묘하게 속도가 느린 코드를 마주할 때가 있습니다. "컴퓨터 성능이 좋으니 괜찮겠지?"라고 안일하게 생각할 수도 있지만, 사용자가 늘어나고 데이터가 쌓이는 순간 그 코드는 시스템 전체를 마비시키는 시한폭탄이 될 수 있습니다. 좋은 개발자와 평범한 개발자를 가르는 기준, 바로 효율성(Efficiency)을 판단하는 척도가 시간 복잡도(Time Complexity)입니다. 오늘은 복잡한 수식 없이, 빅오 표기법(Big-O Notation)의 핵심 개념인 O(1)과 O(n)의 차이를 명확하게 정리해 드립니다.
1. 시간 복잡도란? (시간이 아니라 '횟수'다)
많은 분들이 '시간 복잡도'라는 단어를 듣고 오해하는 것이 있습니다. 바로 알고리즘이 실행되는 절대적인 시간(초 단위)을 의미한다고 생각하는 것입니다. 하지만 이는 정확한 정의가 아닙니다. 코드가 실행되는 시간은 사용하는 컴퓨터의 CPU 성능, 메모리 용량, 현재 실행 중인 다른 프로그램의 영향 등 외부 요인에 따라 천차만별로 달라지기 때문입니다.
1-1. 연산 횟수의 증가 패턴
따라서 컴퓨터 과학에서는 '몇 초가 걸리는가' 대신 '입력 데이터(n)가 늘어날 때, 연산 횟수가 몇 배로 늘어나는가'에 주목합니다. 데이터가 10배 늘어났을 때 연산 횟수도 10배 늘어나는지, 아니면 100배 늘어나는지, 혹은 전혀 늘어나지 않는지를 따지는 것이죠. 이 변화의 추세를 수학적으로 표현한 것이 바로 시간 복잡도입니다.
1-2. 왜 '최악의 경우(Big-O)'를 따질까?
알고리즘의 성능을 표기하는 방법에는 최선(Big-Ω, 오메가), 평균(Big-θ, 세타), 최악(Big-O, 빅오)이 있습니다. 개발자는 항상 최악의 시나리오를 대비해야 합니다. "운이 좋으면 1초 만에 끝납니다"라는 말보다는, "데이터가 아무리 꼬여 있어도 10초 안에는 무조건 끝납니다"라는 보장이 시스템의 안정성 측면에서 훨씬 중요하기 때문입니다. 그래서 우리는 빅오(Big-O) 표기법을 표준으로 사용합니다.
2. O(1): 상수 시간 (Constant Time) - 꿈의 속도
O(1)은 입력 데이터의 크기($n$)와 상관없이 언제나 일정한 속도를 유지하는 가장 이상적인 복잡도입니다. 데이터가 1개일 때나 100억 개일 때나 처리 속도가 똑같다는 뜻입니다.
2-1. 현실의 예시: 열쇠로 문 열기
여러분이 100개의 방이 있는 호텔에 갔다고 상상해 봅시다. 여러분이 가진 카드키는 101호 방문을 바로 열 수 있습니다. 호텔의 방이 1,000개로 늘어난다고 해서 101호를 여는 시간이 늘어날까요? 아닙니다. 방의 개수와 상관없이 문을 여는 동작은 딱 한 번이면 끝납니다. 이것이 O(1)입니다.
2-2. 코드 예시 (JavaScript)
// 배열의 인덱스 접근
const numbers = [10, 20, 30, 40, 50];
function getFirstItem(arr) {
return arr[0]; // 배열 길이가 아무리 길어도 1번 만에 찾음
}
배열의 인덱스(Index)를 알고 있다면, 컴퓨터는 해당 메모리 주소로 즉시 이동하여 값을 가져옵니다. 데이터 양에 전혀 영향을 받지 않는 매우 효율적인 방식입니다.
3. O(n): 선형 시간 (Linear Time) - 정직한 속도
[Image of O(n) complexity graph]
O(n)은 입력 데이터의 크기에 정비례하여 처리 시간이 늘어나는 구조입니다. 데이터가 10배 많아지면 처리 시간도 정확히 10배 더 걸립니다. 가장 직관적이고 흔하게 볼 수 있는 형태입니다.
3-1. 현실의 예시: 책 페이지 넘기기
소설책에서 특정 문장을 찾는다고 가정해 봅시다. 만약 페이지를 1페이지부터 순서대로 넘기며 찾는다면(순차 탐색), 책이 두꺼울수록 찾는 시간은 비례해서 늘어날 것입니다. 최악의 경우 마지막 페이지에 문장이 있다면 책 전체를 다 훑어야 합니다.
3-2. 코드 예시 (JavaScript)
// 반복문을 통한 탐색
function findNumber(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return true;
}
}
return false;
}
위 코드의 `for` 반복문은 배열의 길이(`arr.length`)만큼 반복됩니다. 데이터가 100만 개라면 최대 100만 번의 연산을 수행해야 합니다. 그래프로 그리면 우상향하는 직선이 그려집니다.
4. O(1)과 O(n)의 결정적 차이와 스케일러빌리티
개발자가 스케일러빌리티(Scalability, 확장성)를 고려할 때 이 두 복잡도의 차이는 매우 큽니다.
- 데이터가 적을 때: $n=10$일 때, O(1)은 1번, O(n)은 10번 연산합니다. 사람이 느끼기에 속도 차이는 거의 없습니다 (0.00001초 차이).
- 데이터가 많을 때: $n=100억$일 때, O(1)은 여전히 1번 연산하지만, O(n)은 100억 번 연산합니다. O(1) 알고리즘이 0.1초 만에 끝날 때, O(n) 알고리즘은 며칠이 걸릴 수도 있습니다.
4-1. O(n^2)은 피해야 한다
참고로 이중 반복문(for문 안에 for문)을 사용하면 O(n^2), 즉 이차 시간 복잡도가 됩니다. 데이터가 100배 늘어나면 시간은 10,000배($100^2$) 늘어납니다. 이는 대용량 처리에서 시스템을 다운시키는 주범이므로, 가능한 한 O(n)이나 O(log n) 방식으로 개선(Refactoring)해야 합니다.
1. 시간 복잡도는 데이터 양($n$)에 따른 연산 횟수의 증가율을 나타냅니다.
2. O(1)은 데이터 양과 무관하게 즉시 처리되는 최고의 효율(상수 시간)입니다.
3. O(n)은 데이터 양에 비례하여 시간이 늘어나는 일반적인 반복문(선형 시간)입니다.
4. 대용량 트래픽 환경에서는 O(n)을 O(log n)이나 O(1)로 줄이는 것이 성능 최적화의 핵심입니다.