알고리즘 공부를 시작하면 가장 먼저 마주치는 외계어가 바로 `O(n)`, `O(log n)` 같은 빅오 표기법(Big-O Notation)입니다. "코드가 돌아가기만 하면 됐지, 왜 이런 수학 기호까지 알아야 해?"라고 생각할 수 있지만, 이는 내 코드의 성적표와 같습니다. 내가 짠 코드가 1초 만에 실행될지, 아니면 1년이 걸릴지를 예측할 수 있게 해주는 유일한 척도이기 때문입니다. 오늘은 수학적 정의는 잠시 접어두고, 개발자 관점에서 시간 복잡도를 아주 쉽고 직관적으로 이해해 보겠습니다.
1. 시간 복잡도란? (절대 시간이 아니다)
많은 초보자가 오해하는 것이 있습니다. 시간 복잡도는 코드가 실행되는 '초(Seconds)'를 의미하지 않습니다. 컴퓨터의 사양(CPU, RAM)이 좋을수록 실행 시간은 빨라지기 때문에, 절대적인 시간은 기준이 될 수 없기 때문입니다.
대신 시간 복잡도는 "입력 데이터($n$)가 늘어날 때, 연산 횟수가 몇 배로 늘어나는가?"라는 증가율을 나타냅니다. 데이터가 10배 늘었을 때 연산도 10배 늘어나면 좋은 코드지만, 연산이 100배($10^2$) 늘어난다면 위험한 코드라고 판단하는 식입니다.
2. 빅오(Big-O) 표기법: 최악의 상황을 대비하라
알고리즘의 성능을 나타낼 때는 최선(Best), 평균(Average), 최악(Worst)의 경우가 있습니다. 우리는 항상 최악의 경우(Big-O)를 기준으로 삼습니다. "운 좋으면 1초 만에 찾아요"라는 말보다는, "데이터가 아무리 꼬여 있어도 최대 10초 안에는 무조건 찾습니다"라는 보장이 시스템 안정성에 훨씬 중요하기 때문입니다.
3. O(1): 상수 시간 (Constant Time) - 꿈의 속도
O(1)은 입력 데이터의 크기($n$)와 상관없이 항상 일정한 속도를 내는 알고리즘입니다.
3-1. 예시: 배열의 인덱스 접근
여러분이 도서관 사서라고 가정해 봅시다. "3번 책장에 있는 책을 가져오세요"라는 요청을 받았다면, 도서관에 책이 100권이든 100만 권이든 상관없이 곧바로 3번 책장으로 가서 가져올 수 있습니다.
function getFirstItem(arr) {
return arr[0]; // 데이터가 10억 개여도 1번 만에 끝남
}
이처럼 데이터 양에 영향을 받지 않는 가장 이상적이고 빠른 상태입니다.
4. O(n): 선형 시간 (Linear Time) - 정직한 속도
O(n)은 입력 데이터의 양에 정비례하여 시간이 늘어나는 알고리즘입니다. 그래프를 그리면 우상향하는 직선이 됩니다.
4-1. 예시: 책 찾기 (검색)
도서관에 책들이 아무 순서 없이 마구잡이로 꽂혀 있습니다. 여기서 "해리포터" 책을 찾으려면 어떻게 해야 할까요? 첫 번째 책부터 마지막 책까지 하나하나 제목을 확인해야 합니다. 책이 10배 많아지면, 찾는 시간도 정확히 10배 늘어납니다.
function findValue(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return true;
}
}
우리가 흔히 쓰는 `for` 반복문이 바로 대표적인 O(n)입니다.
5. O(n) vs O(1)의 차이는 언제 느껴질까?
데이터가 적을 때($n=10$)는 O(1)이나 O(n)이나 찰나의 순간이라 차이가 없습니다. 하지만 빅데이터 환경($n=10억$)이 되면 이야기가 달라집니다.
- O(1): 여전히 0.1초 소요.
- O(n): 수 시간 혹은 며칠 소요.
따라서 개발자는 반복문(O(n))을 사용할 때 "이게 최선인가? 해시 테이블을 써서 O(1)로 줄일 순 없을까?"를 항상 고민해야 합니다. 이 고민의 깊이가 곧 개발자의 실력입니다.
1. 시간 복잡도는 데이터 증가에 따른 연산 횟수의 증가 패턴을 의미합니다.
2. O(1)은 데이터 양과 무관하게 즉시 결과를 내는 최고의 효율성(인덱스 접근 등)을 가집니다.
3. O(n)은 데이터 양에 비례해 시간이 늘어나는 일반적인 반복문(탐색 등) 구조입니다.