1,000마리에서 멀쩡하던 코드가 10,000마리에서 죽는다

2026년 9월 15일2026년 9월 18일 수정–최적화

적 1,000마리를 띄우고 서로 겹쳤는지 검사하는 코드를 짰습니다. 잘 돕니다. 기획이 10,000마리로 늘려 달라고 합니다. 적은 열 배가 됐는데 프레임은 열 배가 아니라 백 배 가까이 무거워집니다.

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

왜 초를 재지 않는가

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

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

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

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

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

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배	모든 쌍을 서로 비교하기

숫자로 보면 이렇습니다.

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

같은 결과, 다른 기울기

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

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

최악과 평균은 다르다

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) 보다 빠릅니다. 해시를 계산하고 칸을 찾아가는 상수 비용이 열 번 비교보다 크고, 배열은 메모리가 붙어 있어서 캐시에 통째로 올라오기 때문입니다.

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

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

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

공간도 같이 읽는다

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

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

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

정리

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

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

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

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