---
title: "1,000마리에서 멀쩡하던 코드가 10,000마리에서 죽는다"
description: "초를 재는 대신 입력이 커질 때 연산이 몇 번으로 늘어나는지를 셉니다. Big-O 를 읽는 법, 최악과 평균이 갈리는 자리, 그리고 기울기가 좋은 쪽이 지는 구간까지."
author: "유니얼"
pubDate: 2026-09-15
updatedDate: 2026-09-18
category: "programming/algorithm/graph"
tags: ["최적화"]
canonical: https://blog.unialgames.com/posts/algo-time-complexity/
---
적 1,000마리를 띄우고 서로 겹쳤는지 검사하는 코드를 짰습니다. 잘 돕니다.
기획이 10,000마리로 늘려 달라고 합니다. 적은 열 배가 됐는데 프레임은 열 배가 아니라 백 배 가까이 무거워집니다.

코드는 한 줄도 안 바뀌었습니다. 바뀐 것은 입력의 크기뿐입니다.
**어떤 코드는 입력이 커질 때 같이 커지고, 어떤 코드는 훨씬 빠르게 커집니다.**
그 차이를 적는 방법이 **시간 복잡도**이고, `O(n)` 처럼 쓰는 표기를 **빅오 표기법(Big-O notation)** 이라고 부릅니다.

## 왜 초를 재지 않는가

재는 것은 필요합니다. 다만 잰 값은 그 기기의, 그 순간의, 그 입력에서의 숫자입니다.

- 같은 코드가 내 PC 에서 2ms, 저사양 폰에서 20ms 입니다
- 에디터에서 잰 값과 빌드에서 잰 값이 다릅니다
- 백그라운드에서 뭐가 하나 돌기만 해도 흔들립니다

그래서 "이 코드는 3ms 다" 는 설계를 고르는 기준이 못 됩니다. 기기가 바뀌면 다시 재야 하니까요.
대신 **입력이 커질 때 일의 양이 어떻게 늘어나는가**를 적습니다. 이건 기기와 무관합니다.
적이 열 배가 되면 비교가 백 배가 된다는 사실은 어느 기기에서도 똑같습니다.

## 세는 것은 횟수가 아니라 증가율

리스트를 한 번 훑으면서 각 원소에 몇 가지 일을 하는 코드를 보겠습니다.

```csharp
int total = 0;               // 1번
foreach (var e in enemies) { // n번 반복
    total += e.Hp;           //   1번
    total -= e.Shield;       //   1번
}
return total;                // 1번
```

연산을 그대로 세면 `2n + 2` 입니다. 그런데 복잡도로는 `O(n)` 이라고 적습니다.
계수 2 와 상수 2 를 버립니다. 버리는 이유는 n 이 커지면 그것들이 결론을 못 바꾸기 때문입니다.

| n | 2n + 2 | n 제곱 |
| --- | --- | --- |
| 10 | 22 | 100 |
| 1,000 | 2,002 | 1,000,000 |
| 100,000 | 200,002 | 10,000,000,000 |

n 이 10 일 때는 계수가 붙은 쪽이 오히려 더 큽니다. n 이 커질수록 차이는 벌어지기만 합니다.
**시간 복잡도는 n 이 충분히 커졌을 때의 모양**을 적는 표기라서, 가장 빠르게 자라는 항 하나만 남기고 나머지를 버립니다.
`3n² + 100n + 5000` 은 `O(n²)` 입니다.

버린 것들이 실제로는 존재한다는 점은 기억해 둬야 합니다. 상수가 결론을 뒤집는 구간이 따로 있습니다.

## 자주 나오는 다섯

| 표기 | 이름 | n 이 10배가 되면 | 어디서 만나나 |
| --- | --- | --- | --- |
| `O(1)` | 상수 | 그대로 | 배열 인덱스 접근, Dictionary 조회 |
| `O(log n)` | 로그 | 세 번쯤 더 | 정렬된 배열에서 이진 탐색, 힙에서 하나 꺼내기 |
| `O(n)` | 선형 | 10배 | 리스트 한 번 훑기, 최댓값 찾기 |
| `O(n log n)` | 선형 로그 | 10배보다 조금 더 | 정렬 |
| `O(n²)` | 제곱 | 100배 | 모든 쌍을 서로 비교하기 |

숫자로 보면 이렇습니다.

<x-calc>
<script type="application/json">
{
  "label": "직접 해보기",
  "inputs": [
    { "id": "n", "label": "원소 수", "options": [10, 100, 1000, 10000], "default": 100, "suffix": "개" }
  ],
  "bars": [
    { "label": "log n", "expr": "Math.log2(n)", "unit": "번", "decimals": 0 },
    { "label": "n", "expr": "n", "unit": "번", "decimals": 0 },
    { "label": "n log n", "expr": "n * Math.log2(n)", "unit": "번", "decimals": 0 },
    { "label": "n 제곱", "expr": "n * n", "unit": "번", "decimals": 0, "accent": true }
  ],
  "note": "막대는 서로의 비율만 보여줍니다. 연산 한 번에 걸리는 시간은 종류마다 다릅니다"
}
</script>
</x-calc>

원소가 10개일 때는 넷이 다 고만고만합니다. 10,000개로 올리면 `log n` 막대는 보이지도 않고 `n 제곱`만 남습니다.
**작은 입력에서는 무엇을 골라도 티가 안 나고, 큰 입력에서는 그것만 보입니다.**
그래서 "지금 잘 도는데요" 는 아무것도 보증하지 않습니다. 물어야 할 것은 지금이 아니라 열 배가 됐을 때입니다.

## 같은 결과, 다른 기울기

적 목록에 중복된 ID 가 있는지 검사하는 코드입니다. 결과는 둘 다 같습니다.

<x-compare>
<script type="application/json">
{
  "tabs": [
    {
      "label": "모든 쌍 비교",
      "code": "for (int i = 0; i < ids.Count; i++)\n    for (int j = i + 1; j < ids.Count; j++)\n        if (ids[i] == ids[j])\n            return true;\n\nreturn false;",
      "stats": [["복잡도", "O(n 제곱)"], ["1,000개일 때", "약 50만 번"], ["10,000개일 때", "약 5,000만 번"]],
      "tone": "bad"
    },
    {
      "label": "본 것을 기억하기",
      "code": "var seen = new HashSet<int>(ids.Count);\n\nforeach (int id in ids)\n    if (!seen.Add(id))\n        return true;\n\nreturn false;",
      "stats": [["복잡도", "O(n)"], ["1,000개일 때", "1,000번"], ["10,000개일 때", "10,000번"]],
      "tone": "good"
    }
  ]
}
</script>
</x-compare>

위쪽은 원소 수가 열 배가 되면 비교가 백 배가 됩니다. 아래쪽은 열 배가 됩니다.
**기울기를 바꾼 대가로 메모리를 냈습니다.** 원소 수만큼의 집합을 하나 더 들고 있어야 합니다.
복잡도를 낮추는 일은 대개 이런 맞바꿈입니다. 공짜로 내려가는 경우는 드뭅니다.

## 최악과 평균은 다르다

`HashSet` 과 `Dictionary` 의 조회를 `O(1)` 이라고 적었는데, 정확히는 평균이 그렇습니다.
해시가 고루 흩어지면 칸 하나만 보면 되지만, 모든 키가 같은 칸으로 몰리면 그 칸에 달린 것을 전부 훑게 됩니다. 최악은 `O(n)` 입니다.

| 연산 | 평균 | 최악 | 최악이 나오는 조건 |
| --- | --- | --- | --- |
| Dictionary 조회 | `O(1)` | `O(n)` | 해시 코드가 한 칸으로 몰림 |
| List 의 Add | `O(1)` | `O(n)` | 내부 배열이 꽉 차서 복사가 일어남 |
| List 의 Remove | `O(n)` | `O(n)` | 뒤를 전부 당김 |
| 퀵 정렬 | `O(n log n)` | `O(n 제곱)` | 기준값이 매번 한쪽 끝 |

**프레임 단위로 도는 코드에서는 평균보다 최악이 중요할 때가 많습니다.**
평균 0.1ms 에 백 프레임에 한 번 8ms 가 나오는 코드는, 평균 0.5ms 로 꾸준한 코드보다 나쁘게 느껴집니다.
숫자는 전자가 좋은데 화면에서는 튀는 쪽만 보입니다.

직접 만든 타입을 Dictionary 의 키로 쓸 때 `GetHashCode` 를 대충 짜면 최악이 그냥 현실이 됩니다.
모든 키가 같은 값을 돌려주면 그 Dictionary 는 리스트와 같습니다. 컴파일도 되고 결과도 맞습니다. 느려질 뿐입니다.

## 기울기가 전부는 아니다

복잡도는 상수를 버리고 적은 값입니다. 버린 상수가 결론을 뒤집는 구간이 실제로 있습니다.

원소 열 개짜리 목록에서 하나를 찾는다면, 배열을 처음부터 훑는 `O(n)` 이 Dictionary 의 `O(1)` 보다 빠릅니다.
해시를 계산하고 칸을 찾아가는 상수 비용이 열 번 비교보다 크고, 배열은 메모리가 붙어 있어서 캐시에 통째로 올라오기 때문입니다.

그래서 판단은 두 단계입니다.

1. **n 이 얼마나 커지는가.** 커지지 않는다면 단순한 쪽이 낫습니다. 코드가 짧고 버그가 적습니다
2. **커진다면 기울기를 본다.** 열 배가 됐을 때 백 배가 되는 코드는 지금 멀쩡해도 나중에 터집니다

두 방식이 뒤집히는 지점을 **손익분기점**이라고 부릅니다. 이 값은 상수에 달려 있어서 계산으로 나오지 않습니다.
실제로 재 봐야 나옵니다. 여기서 복잡도와 측정이 각자의 자리를 갖습니다.
**복잡도는 무엇을 고를지 좁혀 주고, 측정은 그중 어느 것이 이 기기에서 이기는지 말해 줍니다.**

## 공간도 같이 읽는다

시간 복잡도와 같은 방식으로 메모리도 적습니다. 입력이 n 일 때 추가로 쓰는 메모리가 얼마나 늘어나는가입니다.

- 배열 하나를 제자리에서 뒤집는 것은 `O(1)` 입니다. 임시 변수 하나면 됩니다
- 방문 여부를 배열에 적어 두는 탐색은 `O(n)` 입니다
- 격자를 한 장 더 만들어 두는 알고리즘은 격자 크기만큼 더 씁니다

**시간을 줄이려고 메모리를 내는 맞바꿈이 대부분입니다.** 위의 중복 검사도 집합 하나를 더 들고 비교를 줄인 것이고,
한 번 계산한 결과를 저장해 두고 다시 쓰는 방식도 같은 거래입니다.
모바일처럼 메모리 여유가 없는 쪽에서는 이 거래가 항상 이득은 아닙니다.

## 정리

시간 복잡도는 코드가 몇 초 걸리는지가 아니라 **입력이 커질 때 일의 양이 어떤 모양으로 늘어나는지**를 적은 것입니다.
기기가 바뀌어도 그 모양은 안 바뀌기 때문에, 코드를 짜기 전에 무엇을 고를지 정하는 데 씁니다.

읽을 때 챙길 것은 셋입니다.

- **가장 빠르게 자라는 항만 남는다.** `3n² + 100n` 은 `O(n²)` 이고, 버린 상수는 작은 입력에서만 의미가 있습니다
- **평균과 최악이 다르다.** 프레임마다 도는 코드에서는 최악이 그대로 프레임 튐이 됩니다
- **기울기가 좋은 쪽이 항상 이기지는 않는다.** 뒤집히는 지점이 어디인지는 재 봐야 압니다

n 이 커지지 않는 자리에서는 복잡도를 따지는 것보다 단순하게 짜는 편이 낫습니다.
따져야 하는 자리는 n 이 기획에 따라 열 배가 될 수 있는 자리입니다.