📚 지식 노트

빅오 표기: 입력이 커질 때의 모양

같은 문제를 푸는 두 코드 중 어느 쪽이 빠른지는 컴퓨터, 언어, 입력에 따라 달라진다. 그래서 알고리즘은 초 단위 대신 입력 크기 n이 커질 때 걸음 수가 어떤 모양으로 늘어나는지로 비교한다. 빅오 표기(Big-O notation)는 그 모양의 위쪽 한계를 적는 약속이다. f(n) = O(g(n))은 충분히 큰 n에서 f(n)이 g(n)의 상수 배를 넘지 않는다는 뜻이다.

그래서 상수와 작은 항은 버린다. 3n² + 100n + 7은 O(n²)이다. n이 작을 때는 100n이 더 커 보여도, n이 수천을 넘으면 n²이 나머지를 모두 덮는다. 정확히는 빅오는 위쪽 한계, 빅오메가(Ω)는 아래쪽 한계, 빅세타(Θ)는 둘 다를 뜻하지만, 실무에서 "이 코드는 O(n log n)이다"라고 할 때는 보통 Θ의 뜻으로 쓴다.

어림셈으로 컴퓨터는 1초에 단순 연산을 대략 10⁸~10⁹번 한다. n이 100만이면 O(n log n)은 눈 깜짝할 사이지만 O(n²)은 몇십 분에서 몇 시간이 걸린다. 그래서 문제를 받으면 먼저 n의 크기를 보고, 그 크기에서 허용되는 복잡도부터 정한다. 정렬이 왜 O(n log n)보다 빠를 수 없는지(비교 정렬의 하한)는 정렬과 탐색 노트에서 다룬다.

메모리도 같은 방식으로 잰다. 입력 말고 추가로 쓰는 메모리를 공간 복잡도(space complexity)라 한다. 병합 정렬은 시간 O(n log n)에 공간 O(n)을, 힙 정렬은 같은 시간에 공간 O(1)을 쓴다. 빠른 쪽이 늘 이기는 것은 아니고, 메모리가 빠듯한 곳에서는 공간이 먼저다.

• 로그의 밑은 적지 않는다: log₂ n과 log₁₀ n은 밑 변환 공식에 따라 상수배(약 3.32배)만 다르므로 빅오에서는 똑같이 O(log n)이다. 지수의 밑은 다르다. 2ⁿ과 3ⁿ은 비가 (3/2)ⁿ으로 끝없이 벌어지니 서로 다른 복잡도다.
• 입력이 둘이면 둘 다 적는다: 길이 n과 m인 두 배열을 차례로 훑으면 O(n + m), 모든 쌍을 비교하면 O(nm)이다. 한쪽이 훨씬 작다는 보장이 없으면 n 하나로 뭉뚱그리지 않는다. 그래프 알고리즘의 O(V + E)가 같은 꼴이다.
• O(1)이 늘 빠른 것은 아니다: 빅오는 상수를 버리므로, 해시를 계산하고 캐시 미스를 내는 O(1) 찾기가 원소 몇 개짜리 배열을 훑는 O(n)보다 느릴 수 있다. 차수는 n이 커질 때의 이야기다.

문제 풀기 →Python 코드 →

최선·평균·최악

같은 알고리즘도 입력이 어떻게 생겼느냐에 따라 걸음 수가 다르다. 배열을 앞에서부터 하나씩 보는 선형 탐색(linear search)은 찾는 값이 맨 앞이면 한 번에 끝나고, 없으면 n칸을 모두 본다. 이 셋을 최선(best case), 평균(average case), 최악(worst case)이라 부른다.

보통 가장 중요한 것은 최악이다. 최악이 보장되면 어떤 입력이 와도 그보다 느리지 않다. 평균은 "입력이 고르게 섞여 온다" 같은 가정을 깔고 계산하므로, 가정이 깨지면 의미가 없다. 퀵 정렬은 평균 O(n log n)이지만 이미 정렬된 배열에 순진한 기준값을 쓰면 O(n²)으로 무너진다. 공격자가 입력을 고를 수 있는 서버라면 이런 최악을 일부러 만들어 낸다.

최선은 거의 쓸모가 없다. 어떤 알고리즘이든 운 좋은 입력 하나쯤은 있기 때문이다. 다만 "이미 거의 정렬된 입력"처럼 실제로 자주 오는 좋은 경우가 있다면 그때의 속도(삽입 정렬의 O(n))가 고르는 이유가 되기도 한다.

문제 풀기 →Python 코드 →

분할 상환 분석: 가끔 비싼 연산을 나눠 내기

어떤 연산은 대부분 싸고 아주 가끔 비싸다. 크기가 늘어나는 배열인 동적 배열(dynamic array; C++의 vector, Java의 ArrayList, 파이썬의 list)이 그렇다. 빈 자리가 있으면 끝에 쓰기만 하면 되지만(O(1)), 가득 차면 더 큰 메모리를 새로 잡고 기존 값을 전부 옮겨야 한다(O(n)). 그렇다면 넣기는 O(n)일까?

분할 상환 분석(amortized analysis)은 연산 하나가 아니라 연속된 연산 전체의 비용을 보고 횟수로 나눈다. 용량을 두 배씩 늘리면, n개를 넣는 동안 옮겨 적는 총량은 1 + 2 + 4 + … + n/2 < n이다. 여기에 쓰기 n번을 더해도 3n을 넘지 않으니, 넣기 한 번의 분할 상환 비용은 O(1)이다.

핵심은 늘리는 비율이다. 두 배(또는 1.5배)처럼 곱으로 늘려야 옮기는 일이 등비수열이 되어 합이 n에 비례한다. 매번 10칸씩 더하는 식으로 늘리면 옮기는 총량이 n²/20 정도가 되어 넣기가 O(n)으로 돌아간다. 대신 곱으로 늘리면 최대 절반 가까이 빈 칸을 들고 있으니, 메모리를 시간과 바꾸는 셈이다.

분할 상환은 평균과 다르다. 평균은 입력의 확률을 가정하지만, 분할 상환은 어떤 순서로 넣어도 성립하는 보장이다. 다만 개별 연산은 여전히 가끔 느리다. 게임의 한 프레임처럼 매번 마감이 있는 곳에서는 그 한 번이 끊김(hitch)이 되므로, 크기를 미리 잡아 두는(reserve) 편이 안전하다.

문제 풀기 →Python 코드 →

메모리 계층과 캐시 지역성

빅오는 모든 메모리 읽기가 같은 값이라고 가정하지만, 실제 컴퓨터는 그렇지 않다. CPU 안의 L1 캐시는 1나노초 안팎이고 RAM은 수십~100나노초로 거의 100배 느리다. CPU는 RAM에서 값을 하나씩이 아니라 캐시 라인(cache line; 보통 64바이트) 단위로 가져온다. 자세한 계층 구조는 RAM 노트와 CPU 노트에 있다.

그래서 지역성(locality of reference)이 속도를 가른다. 방금 읽은 주소의 이웃을 곧 읽는 것이 공간 지역성, 방금 읽은 값을 곧 다시 읽는 것이 시간 지역성이다. 배열을 순서대로 훑으면 한 라인을 가져올 때마다 이웃 값 여러 개가 공짜로 따라오고, CPU의 하드웨어 프리페처(prefetcher)가 다음 라인까지 미리 당겨 놓는다.

연결 리스트를 따라가는 일을 포인터 추적(pointer chasing)이라 부른다. 다음 노드의 주소는 지금 노드를 읽어야 알 수 있으므로 미리 가져올 수도, 여러 개를 동시에 가져올 수도 없다. 그래서 이론상 복잡도가 같거나 조금 나빠도 배열 기반 자료구조가 실제로는 더 빠른 경우가 많다. 게임 엔진이 객체를 종류별 배열로 늘어놓는 ECS 설계도 같은 이유다(게임 엔진 노트).

실용 규칙은 셋이다. 자주 함께 쓰는 값은 붙여 두고, 큰 2차원 배열은 메모리에 놓인 순서(보통 행 우선)대로 돌고, 꼭 필요하지 않으면 노드마다 따로 할당하지 않는다.

문제 풀기 →Python 코드 →

재귀와 호출 스택

재귀(recursion)는 함수가 더 작은 같은 문제로 자기 자신을 부르는 것이다. 반드시 더 부르지 않고 바로 답하는 바닥 조건(base case)이 있어야 하고, 부를 때마다 문제가 바닥 쪽으로 작아져야 끝난다. 트리 순회, 분할 정복, 백트래킹처럼 문제 자체가 같은 모양으로 쪼개질 때 코드가 짧고 읽기 쉬워진다.

factorial(n):
  if n == 1: return 1           // 바닥 조건
  return n × factorial(n - 1)   // 더 작은 같은 문제

함수를 부르면 실행 환경은 인자, 지역 변수, 돌아갈 자리를 담은 스택 프레임(stack frame)을 호출 스택(call stack) 위에 쌓는다. 함수가 끝나면 그 프레임을 걷어 내고 아래 프레임으로 돌아간다. 마지막에 부른 것이 먼저 끝나는 후입선출(LIFO)이라 스택이라 부른다.

재귀의 비용은 이 스택에 있다. factorial(n)은 시간 O(n)에 스택 공간도 O(n)을 쓴다. 스택은 보통 스레드마다 수 MB로 정해져 있어, 깊이가 수만~수십만을 넘으면 스택 넘침(stack overflow)으로 프로그램이 죽는다. 파이썬은 기본 재귀 한도가 1,000이다. 깊어질 수 있는 재귀는 직접 만든 스택을 쓰는 반복문으로 바꾼다.

또 하나의 함정은 같은 부분 문제를 거듭 푸는 것이다. fib(n) = fib(n-1) + fib(n-2)를 그대로 재귀로 쓰면 호출이 두 갈래로 갈라져 O(2ⁿ)번이 된다. 한 번 푼 답을 기억해 두면(메모이제이션) O(n)으로 줄어든다. 이 생각을 넓힌 것이 설계 기법 노트의 동적 계획법이다.

문제 풀기 →Python 코드 →