카테고리 없음

왕초보를 위한 시간 복잡도: Big-O 표기법 아주 쉽게 이해하기 (O(1) vs O(n))

머니지니87 2026. 2. 21. 11:53
반응형

프로그래밍을 독학하거나 부트캠프에서 개발을 배우다 보면 기능 구현은 어떻게든 해내게 됩니다. 화면에 글자가 뜨고, 데이터베이스에 정보가 저장되는 것을 보면 무척 뿌듯합니다. 하지만 실무에 투입되거나 시니어 개발자에게 코드 리뷰를 받는 순간 가장 많이 듣게 되는 지적 중 하나가 바로 "이 코드는 성능이 너무 안 좋은데요? 시간 복잡도가 어떻게 되죠?"입니다. 기능이 정상적으로 작동하는데 성능이 안 좋다는 것은 무슨 의미일까요? 컴퓨터 공학에서는 내가 작성한 코드가 얼마나 효율적인지 객관적으로 측정하고 소통하기 위해 '시간 복잡도(Time Complexity)'와 '빅오 표기법(Big-O Notation)'이라는 표준 지표를 사용합니다. 복잡한 수학 공식은 잠시 내려놓고, 누구나 이해할 수 있는 아주 쉬운 비유를 통해 빅오 표기법의 개념을 완벽하게 정복해 보겠습니다.

1. 시간 복잡도란 무엇인가? (초가 아니라 '횟수'다)

가장 먼저 바로잡아야 할 오해는 '시간 복잡도'라는 단어에 포함된 '시간'의 의미입니다. 많은 입문자들이 이를 프로그램이 실행되는 절대적인 시간(예: 0.5초, 2초)이라고 착각합니다. 하지만 똑같은 코드를 최신형 맥북에서 돌릴 때와 10년 된 구형 노트북에서 돌릴 때의 속도는 천지 차이일 것입니다. 네트워크 상태나 백그라운드 프로그램의 유무에 따라서도 실행 시간은 매번 달라집니다.

1-1. 절대 시간이 아닌 증가율(Growth Rate)

따라서 컴퓨터 과학에서는 불안정한 절대 시간 대신, "입력되는 데이터의 크기($n$)가 점점 커질 때, 연산(계산)을 수행하는 횟수가 어떤 비율로 늘어나는가?"에 주목합니다. 데이터가 10배 늘어났을 때 연산 횟수도 똑같이 10배 늘어나는지, 100배 늘어나는지, 아니면 데이터 양에 상관없이 항상 일정한 연산만 수행하는지를 따져보는 것입니다. 이 연산 횟수의 증가 추세를 수학적 기호로 간단하게 표현한 것이 바로 시간 복잡도입니다.

1-2. 왜 하필 최악의 경우(Big-O)를 따질까?

알고리즘의 성능을 평가하는 지표에는 최상의 경우를 나타내는 오메가($\Omega$), 평균적인 경우를 나타내는 세타($\Theta$), 그리고 최악의 경우를 나타내는 빅오(Big-$O$)가 있습니다. 소프트웨어 엔지니어링에서는 시스템의 안정성을 담보하는 것이 무엇보다 중요합니다. 운이 좋아 0.1초 만에 데이터 처리가 끝나는 요행을 바라는 것보다, 데이터가 가장 악랄하게 꼬여있는 최악의 상황이 오더라도 "내 코드는 아무리 늦어도 이 정도 시간 안에는 무조건 연산을 끝마칩니다"라고 보장하는 상한선(Upper Bound)을 파악하는 것이 시스템 다운을 막는 필수 요소이기 때문에 우리는 항상 Big-O 표기법을 기준으로 소통합니다.

2. O(1): 상수 시간 (Constant Time) - 마법의 속도

O(1)은 입력 데이터의 크기($n$)와는 전혀 무관하게 항상 일정한 연산 횟수를 보장하는 가장 이상적이고 환상적인 시간 복잡도입니다. 데이터가 10개 있든, 100억 개가 있든 연산 속도는 똑같습니다.

2-1. 현실 비유: 호텔 방 열쇠

여러분이 1,000개의 객실이 있는 거대한 호텔에 방문했다고 상상해 봅시다. 프론트에서 '707호' 열쇠를 받았습니다. 여러분은 호텔 방이 10개든 1,000개든 10만 개든 상관없이 엘리베이터를 타고 7층에 내려 707호 문을 바로 열 수 있습니다. 방의 개수가 늘어난다고 해서 해당 방 번호를 여는 과정이 복잡해지지 않는 것과 같습니다. 데이터 구조 중에서는 배열(Array)과 해시(Hash Table)의 데이터 접근 방식이 이에 해당합니다.

2-2. 코드 예시와 원리 분석


// 자바스크립트 배열 인덱스 접근
const numbers = [10, 20, 30, 40, 50];

function getFirstItem(arr) {
    return arr[0]; // 데이터 길이가 길어져도 즉각 1번 만에 찾아옵니다.
}

배열의 인덱스 접근은 O(1)의 대표적인 방식입니다. 컴퓨터 메모리의 시작 주소만 알고 있다면, 0번째 데이터든 10만 번째 데이터든 단순 수학 계산 한 번만으로 그 메모리 위치로 직행할 수 있는 매우 효율적인 방식입니다.

3. O(n): 선형 시간 (Linear Time) - 정직한 속도

O(n)은 입력 데이터의 양(크기)에 정비례하여 처리해야 할 연산의 횟수가 정직하게 늘어나는 알고리즘입니다. 실무에서 가장 흔하게 접하는 데이터 처리 방식입니다.

3-1. 현실 비유: 책 페이지 하나씩 넘기기

여러분이 도서관에서 "자바스크립트 완전 정복"이라는 두꺼운 책을 찾고 있다고 생각해 봅시다. 책들이 책장에 아무런 규칙 없이 꽂혀있다면, 원하는 책을 발견할 때까지 맨 왼쪽부터 오른쪽으로 제목을 일일이 확인하며 지나가야 합니다. 책이 10배 많아지면, 찾는 데 걸리는 시간도 최대 10배 더 소요될 것입니다. 최악의 경우, 여러분이 찾는 책이 가장 마지막에 있거나 도서관에 아예 없다면 전체 책을 전부 다 검사해야 합니다.

3-2. 코드 예시와 원리 분석


// 순차 탐색 반복문
function findValue(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return true;
    }
}

`for`나 `while` 같은 반복문을 1번 사용하면 데이터 크기 $n$만큼 배열의 길이를 순회해야 합니다. 이러한 순차 탐색을 거치게 되므로, 그래프를 그려보면 우상향하는 일직선의 선형 그래프를 확인할 수 있습니다.

4. O(1)과 O(n)의 데이터 스케일 차이 체감

개발자가 확장성(Scalability)을 고려할 때 이 두 시간 복잡도는 천지 차이입니다.

4-1. 100만 개 데이터일 때의 체감 속도 비교

데이터가 적을 때는 $n=10$ 수준에서 O(1)이 한 번, O(n)이 열 번 연산한다고 하여 체감할 수 있는 속도 차이가 없습니다. 0.0001초나 0.001초의 차이에 불과하니까요. 하지만 사용자 트래픽이 폭증하여 데이터가 수십억 개로 늘어나는 빅데이터 환경을 맞이하면 어떨까요? $n=100억$일 때, O(1) 방식의 데이터 조회는 여전히 즉시 결과를 뱉어내지만, 반복문 탐색 구조인 O(n) 방식은 100억 번의 반복 계산을 해야만 하므로 수 초에서 수 분의 딜레이를 유발하며 시스템 전체를 먹통으로 만들 위험성이 높습니다. 최적화를 위해 끊임없이 시간 복잡도(O($n^2$) -> O($n$) -> O($\log n$) -> O(1))를 낮추려는 노력이 바로 백엔드 개발자의 숙명입니다.

[핵심 요약]
1. 시간 복잡도는 데이터 입력 증가율에 따라 연산 횟수의 비율 변화를 최악의 패턴(Big-O)으로 나타낸 기준입니다.
2. O(1)은 데이터 양과 무관하게 언제나 즉시 연산되는 최고 효율(상수 시간)입니다.
3. O(n)은 데이터 양에 완전히 정비례하여 연산이 늘어나는 가장 일반적인 반복문(선형 시간) 구조입니다.
반응형