1. 빅오 표기법이 말해주는 것
코드를 짜다 보면 이 알고리즘은 오엔이다, 이건 오엔제곱이다 라는 말을 자주 듣게 됩니다. 빅오(Big O)는 입력 크기가 커질 때 연산 횟수가 대략 어떤 비율로 늘어나는지를 나타내는 표기법입니다. 입력 크기는 흔히 n으로 나타내고 O(n), O(n^2)처럼 씁니다. 초 단위 시간을 정확히 재는 게 아니라 데이터가 늘어날 때 연산량이 늘어나는 경향만 보는 도구입니다.
리스트에서 특정 값을 처음부터 하나씩 비교하며 찾는 코드는 데이터가 100개면 최대 100번, 1000개면 최대 1000번 비교합니다. 데이터 개수만큼 비교 횟수가 늘어나기 때문에 이런 연산을 O(n)이라고 씁니다. n은 데이터 개수를 나타내는 변수일 뿐이고, 문제에 따라 리스트 길이일 수도 문자열 길이일 수도 있습니다.
2. 상수와 낮은 차수는 왜 지워버릴까
빅오를 계산하다 보면 이상한 규칙을 만나게 됩니다. 연산을 2n+3번 하는 코드도 그냥 O(n)이라고 쓰고, n^2+50n번 하는 코드도 O(n^2)이라고 씁니다. 앞에 붙는 숫자나 덜 중요한 항을 통째로 무시해버리는 셈인데, n이 충분히 커지면 가장 크게 늘어나는 항 하나가 전체 결과를 사실상 다 결정하기 때문입니다.
숫자로 보면 더 잘 와닿습니다. n이 10이면 2n+3은 23이고 n^2+50n은 600입니다. n이 백만이면 2n+3은 200만 남짓인데 n^2+50n은 1조에 5000만을 더한 값이 됩니다. 200만에 3이 붙었는지는 결과에 영향이 없고, 1조짜리 숫자에 5000만이 더해지든 말든 눈에 들어오지도 않습니다. 그래서 빅오는 n이 충분히 커진 상황을 기준으로 가장 영향력이 큰 항만 남깁니다.
3. 자주 보는 빅오 순서 감으로 익히기
코딩테스트나 면접에서 자주 등장하는 빅오는 정해져 있습니다. 작은 쪽부터 나열하면 O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n) 순서입니다. O(1)은 데이터가 얼마나 많든 걸리는 시간이 항상 똑같은 경우로 인덱스로 값을 꺼내는 연산이 그렇습니다. O(log n)은 절반씩 줄여가며 확인하는 이진 탐색이 대표적이고, O(n)은 한 번씩 훑는 경우, O(n log n)은 정렬처럼 n번 반복하며 매번 log n만큼 더 일하는 경우입니다.
뒤로 갈수록 얼마나 무서워지는지 파이썬으로 직접 확인해 보겠습니다.
n_values = [10, 40]
for n in n_values:
print(n, "일 때 n제곱은", n ** 2, ", 2의 n제곱은", 2 ** n)
10 일 때 n제곱은 100 , 2의 n제곱은 1024
40 일 때 n제곱은 1600 , 2의 n제곱은 1099511627776
n이 10에서 40으로 네 배 늘었을 뿐인데 n^2은 16배 정도 늘어난 반면 2^n은 상상하기 어려운 수준으로 폭발합니다. 그래서 모든 경우의 수를 다 따지는 O(2^n) 완전탐색 코드는 n이 20을 넘어가면 이미 위험 신호로 받아들여야 합니다.
4. 빅오는 실제 실행 시간표가 아니다
빅오를 처음 배울 때 흔한 오해는 O(n) 코드가 O(n^2) 코드보다 항상 빠르다고 믿는 것입니다. 빅오는 상수를 지워버린 표기법이라 작은 n에서는 결과가 뒤집히기도 합니다. O(n) 코드가 반복마다 무거운 작업을 백 번씩 하고 O(n^2) 코드는 반복마다 가벼운 작업 한 번만 한다면, n이 열 개 정도로 작을 때는 오히려 O(n^2) 쪽이 더 빨리 끝날 수도 있습니다. n이 수백만 단위로 커지면 이 차이가 확실히 드러나지만, n이 몇 개 안 되는 작은 문제에서는 빅오만 보고 단정하면 안 됩니다.
5. 최선, 평균, 최악은 서로 다른 이야기
빅오 하나만 보고 이 알고리즘은 항상 이 속도로 동작한다고 오해하기 쉽습니다. 빅오는 입력이 어떻게 주어지느냐에 따라 최선, 평균, 최악 세 가지로 나뉘어 이야기되는 경우가 많습니다. 정렬 알고리즘인 퀵 정렬이 자주 드는 예인데, 평균은 O(n log n)이지만 데이터가 이미 정렬된 경우처럼 운이 나쁘면 O(n^2)까지 느려집니다.
def find_value(nums, target):
for i, num in enumerate(nums):
if num == target:
return i
return -1
찾는 값이 맨 앞에 있으면 비교 한 번으로 끝나니 최선은 O(1)에 가깝고, 맨 뒤에 있거나 아예 없으면 끝까지 다 훑어야 하니 최악은 O(n)입니다. 코드는 그대로인데 입력에 따라 걸리는 시간이 달라진다는 뜻입니다.
6. 반복문 개수보다 실제로 몇 번 도는지가 중요하다
코드를 보고 빅오를 판단할 때 반복문이 몇 겹인지부터 세는 습관이 있는데, 이건 절반만 맞는 방법입니다. 진짜 기준은 반복문이 실제로 몇 번 실행되느냐입니다.
def print_pairs(nums):
n = len(nums)
for i in range(n):
for j in range(3):
print(nums[i], j)
반복문이 두 겹으로 겹쳐 있지만 안쪽 반복문은 항상 딱 3번만 돕니다. 데이터가 아무리 늘어나도 안쪽 반복 횟수는 그대로이니 전체 연산량은 n에 3을 곱한 정도, 여전히 O(n)입니다.
반대로 반복문이 하나뿐이어도 그 안에서 O(n)짜리 연산을 부르면 전체는 O(n^2)이 됩니다. 자주 나오는 예가 파이썬 리스트 맨 앞에 값을 계속 끼워 넣는 코드입니다.
result = []
for num in range(10000):
result.insert(0, num)
insert(0, num)은 새 값을 넣을 자리를 만들려고 기존 원소를 전부 한 칸씩 뒤로 밀어야 해서 그 자체로 O(n)입니다. 이걸 만 번 부르면 O(n) 곱하기 O(n)이 되어 전체는 O(n^2)이 됩니다. 반복문이 하나뿐이라 O(n)처럼 보이지만 실제로는 훨씬 느리게 동작하는 대표적인 함정입니다.
7. 공간복잡도도 같이 챙겨야 한다
지금까지 이야기한 내용은 전부 시간복잡도, 연산 횟수에 관한 것이었습니다. 알고리즘을 평가할 때는 추가로 쓰는 메모리양도 함께 봐야 하는데, 이를 공간복잡도라고 부릅니다.
def make_squares(nums):
result = []
for num in nums:
result.append(num * num)
return result
이 함수는 nums와 별개로 result라는 새 리스트를 만들어 nums 길이만큼 값을 채웁니다. 입력이 커질수록 새로 쓰는 메모리도 늘어나 공간복잡도는 O(n)입니다. 반면 기존 리스트 값을 그 자리에서 바로 바꾸면 추가 메모리가 거의 안 들어 O(1)이 됩니다. 시간을 줄이려고 메모리를 넉넉히 쓰는 경우도 많아 시간과 공간은 종종 맞바꾸는 관계입니다.
8. 제한 조건을 보고 목표 복잡도 거꾸로 잡기
실전에서 빅오가 가장 쓸모 있어지는 순간은 입력 크기 제한을 보고 어떤 복잡도까지 허용되는지 미리 가늠할 때입니다. 컴퓨터는 대략 1초에 1억 번 정도의 단순 연산을 처리한다고 어림잡습니다.
이 감각으로 거꾸로 계산하면, n이 20 이하면 O(2^n) 완전탐색도 허용되고, n이 5000 정도면 O(n^2) 이중 반복문도 무난히 통과합니다. n이 백만 단위면 O(n^2)은 1조에 가까운 연산이 되어 시간 초과가 확정적이라 O(n)이나 O(n log n)으로 풀어야 합니다. 입력 제한부터 확인하고 목표 복잡도를 세운 뒤 코드를 짜는 습관을 들이면 시간 초과로 좌절하는 일을 크게 줄일 수 있습니다.