개발자 면접 대비 | 시간복잡도 빅오(Big O) 표기법 완벽 정리

O(1) O(n) O(n²) O(log n) 코드 예시와 면접 답변


백엔드 개발을 하다 보면
실무에서 시간복잡도를 직접 쓸 일은 많지 않다.

하지만 코딩테스트나 라이브코딩 면접에서는
"이 코드의 시간복잡도가 어떻게 되나요?"
라는 질문이 거의 반드시 나온다.

이 글에서는 빅오(Big O) 표기법 개념부터
면접에서 실제로 쓰이는 패턴까지 한 번에 정리한다.





빅오(Big O) 표기법이란?

1894년 독일 수학자 파울 바흐만이 처음 사용한 수학 기호다.
O는 독일어 Ordnung, 즉 "차수/크기의 등급"에서 왔다.

원래는 순수 수학 기호였는데
컴퓨터 과학에서 알고리즘 성능을 표현하는 데
그대로 가져다 쓰고 있다.

> 데이터 크기 n이 커질 때,
> 연산 횟수가 어떤 비율로 늘어나는가.




시간복잡도 판단 공식 

루프 없이 바로 접근    →  O(1)
for 루프 1개           →  O(n)
for 루프 2개 중첩      →  O(n²)
절반씩 줄이는 탐색     →  O(log n)
Arrays.sort / 정렬     →  O(n log n)

이 다섯 가지만 알면 면접 질문의 90%는 커버됨


## O(1) — 오 오브 원

속도 ★★★★★

데이터가 몇 개든 항상 같은 시간이 걸린다.
루프도 없고, 탐색도 없다. 그냥 바로 꺼낸다.

```java
// 배열 인덱스 접근
int val = arr[2];  // 항상 1번

// HashMap get
map.get("apple");  // 항상 1번
```

💬 답변
"HashMap으로 바로 꺼내기 때문에 O(1)입니다.
데이터 개수와 무관하게 속도가 일정합니다."


---


## O(n) — 오 엔

속도 ★★★★☆

데이터가 n배 늘면 시간도 n배 걸린다.
for 루프를 한 번 돌면 보통 O(n)이다.

```java
// 리스트 합계
for (int x : list) {
    sum += x;
}

// 값 찾기
for (int i = 0; i < n; i++) {
    if (arr[i] == target) return i;
}
```

💬 답변
"리스트를 한 번 순회하기 때문에 O(n)입니다.
데이터 1000개면 1000번 연산합니다."


---


## O(n²) — 오 엔 스퀘어드

속도 ★★☆☆☆

데이터가 2배 늘면 시간은 4배 걸린다.
for 루프가 이중으로 중첩되면 O(n²)이다.

데이터가 커질수록 급격하게 느려지기 때문에
면접에서는 개선 방법까지 세트로 말하는 게 좋다.

```java
// 이중 for문
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // n × n = n²
    }
}
```

💬 답변
"이중 for문이라 O(n²)입니다.
HashMap을 활용하면 O(n)으로 개선할 수 있습니다."


---


## O(log n) — 오 로그 엔

속도 ★★★★★

매번 탐색 범위를 절반으로 줄인다.
100만 개 데이터도 약 20번이면 찾는다.
이진탐색이 대표적인 예다.

```java
// 이진탐색
while (left <= right) {
    int mid = (left + right) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
    // 매번 탐색 범위가 절반으로 줄어든다
}
```

💬 답변
"이진탐색은 매번 범위를 절반씩 줄이기 때문에
O(log n)입니다.
1000만 개 데이터도 약 23번이면 찾습니다."


---


## O(n log n) — 오 엔 로그 엔

속도 ★★★☆☆

일반적인 정렬 알고리즘의 시간복잡도다.
비교 기반 정렬의 이론적 하한선이기도 하다.

Java의 Arrays.sort(), Collections.sort()가
모두 여기에 해당한다.

```java
Arrays.sort(arr);       // O(n log n)
Collections.sort(list); // O(n log n)
```

💬 답변
"Arrays.sort를 사용했기 때문에 O(n log n)입니다.
비교 기반 정렬의 이론적 하한선이기도 합니다."


---


## 시간복잡도 속도 비교 (n = 1000 기준)

O(1)       →        1회
O(log n)   →       10회
O(n)       →    1,000회
O(n log n) →   10,000회
O(n²)      → 1,000,000회

n이 커질수록 O(n²)은 폭발적으로 느려진다.
대용량 데이터에서 이중 for문을 경계해야 하는
이유가 바로 이것이다.


---


## 마무리

시간복잡도와 빅오 표기법은
코드가 "얼마나 느려지는가"를 표현하는 언어다.

처음엔 낯설지만 패턴만 익히면
코드를 보는 즉시 감이 온다.

면접에서는 복잡도를 말한 뒤
"이렇게 개선할 수 있다"는 방향까지 언급하면
훨씬 인상적인 답변이 된다.


#시간복잡도 #빅오표기법 #BigO #개발자면접 #코딩테스트 #알고리즘 #자바 #Java #백엔드개발 #개발블로그