[자료구조 02] 시간 복잡도와 빅오 표기

어떤 코드가 빠른지 느린지는 실제로 돌려 보기 전에도 가늠할 수 있습니다. 그 가늠자가 시간 복잡도(time complexity)이고, 이를 적는 기호가 빅오 표기법(Big-O notation)입니다. 이름은 거창하지만 뜻은 단순합니다. 데이터가 n개일 때 일의 양이 얼마나 늘어나는가, 그 모양을 보는 것입니다. 이 글에서는 자주 나오는 네 가지 모양을 코드로 하나씩 만져 보고, 실제 반복 횟수까지 세어 몸으로 느껴 보겠습니다.

02.1 빅오는 정확한 시간이 아니라 모양입니다

빅오는 스톱워치로 잰 초가 아닙니다. 같은 코드라도 컴퓨터가 빠르면 빨리 끝나고 느리면 늦게 끝나므로, 초 단위는 상황마다 달라집니다. 빅오가 보는 것은 그런 절대 시간이 아니라, 데이터 개수 n이 늘어날 때 일의 양이 어떤 곡선을 그리며 커지는가입니다. 개수와 상관없이 일정하면 O(1), 개수에 비례하면 O(n), 개수의 제곱으로 폭발하면 O(n의 제곱), 매 단계 범위가 반씩 줄면 O(log n)입니다. 이 네 가지를 순서대로 확인하겠습니다. 뒤에 나오는 예제는 모두 짧으니, 각 코드가 어떤 모양에 해당하는지 생각하며 따라 쳐 보시기 바랍니다.

02.2 O(1), 데이터가 많아도 일정합니다

리스트의 첫 원소를 꺼내는 일은 리스트가 아무리 길어도 걸리는 시간이 같습니다.

def first(lst):

return lst[0]

print(first([10, 20, 30]))

10

인덱스로 콕 집어 꺼내는 접근은 데이터가 3개든 300만 개든 한 번의 동작으로 끝납니다. 몇 번째 자리인지 알면 그 자리로 바로 가기 때문에, 앞의 원소들을 훑을 필요가 없습니다. 이렇게 개수와 무관하게 일정한 시간을 O(1)(상수 시간)이라고 합니다. 빅오 중에서 가장 빠른 등급입니다. 이런 O(1) 동작은 데이터가 커져도 부담이 없으니, 가능하면 O(1)로 해결되는 방법을 찾는 것이 좋습니다.

02.3 O(n), 데이터에 비례합니다

이번엔 리스트의 모든 수를 더해 보겠습니다.

def mysum(lst):

total = 0

for x in lst:

total += x

return total

print(mysum([1, 2, 3, 4, 5]))

15

모든 수를 더하려면 원소를 하나씩 빠짐없이 훑어야 합니다. 그래서 개수가 2배면 더하는 횟수도 2배, 10배면 10배가 됩니다. 이렇게 개수에 곧바로 비례하는 것이 O(n)입니다. 앞 편에서 본 리스트의 값 찾기도 앞에서부터 하나씩 비교하니 바로 이 등급이었습니다. 데이터를 한 번씩 다 봐야 하는 일은 대부분 O(n)이라고 생각하면 됩니다. 화면에 목록을 모두 출력하거나, 합계와 평균을 구하는 일이 전형적인 O(n)입니다. 데이터가 두 배가 되면 걸리는 시간도 대략 두 배가 된다고 보면 크게 틀리지 않습니다.

02.4 O(n의 제곱), 반복 안의 반복

리스트에서 만들 수 있는 모든 짝(쌍)을 구해 보겠습니다.

def pairs(lst):

result = []

for i in range(len(lst)):

for j in range(i + 1, len(lst)):

result.append((lst[i], lst[j]))

return result

print(pairs([1, 2, 3]))

[(1, 2), (1, 3), (2, 3)]

반복문 안에 또 반복문이 들어가 있는 점에 주목하세요. 바깥이 한 바퀴 돌 때마다 안쪽이 통째로 다시 돕니다. 그러면 일의 양이 n 곱하기 n으로 불어나, n이 10배가 되면 시간은 100배가 됩니다. 이것이 O(n의 제곱)이고, 데이터가 커질 때 가장 조심해야 할 모양입니다. 반복문이 두 겹으로 겹쳐 있으면 일단 이 모양을 의심해 보는 습관이 좋습니다. 모든 쌍을 비교하거나 모든 조합을 따지는 문제에서 이 모양이 자주 나옵니다. 데이터가 작을 때는 괜찮지만, 수만 개만 되어도 눈에 띄게 느려집니다.

02.5 숫자로 체감하는 O(n)과 O(n의 제곱)

말로만 들으면 감이 잘 안 옵니다. n을 100과 1000으로 바꿔 가며 실제 반복 횟수를 세어 눈으로 비교해 보겠습니다.

def ops_linear(n):

c = 0

for i in range(n):

c += 1

return c

def ops_quad(n):

c = 0

for i in range(n):

for j in range(n):

c += 1

return c

for n in [100, 1000]:

print(n, "->", ops_linear(n), "회 vs", ops_quad(n), "회")

100 -> 100 회 vs 10000 회

1000 -> 1000 회 vs 1000000 회

n이 10배(100에서 1000)로 늘 때 O(n)은 10배, O(n의 제곱)은 100배로 뜁니다. 왼쪽 숫자는 1000까지 얌전히 늘지만, 오른쪽은 벌써 100만 회입니다. 데이터가 조금만 더 커지면 O(n의 제곱) 쪽은 손을 쓸 수 없을 만큼 느려집니다. 알고리즘의 모양 하나가 얼마나 큰 차이를 만드는지 이 표 하나로 실감이 납니다. 그래서 데이터가 많아질 것 같으면, O(n의 제곱)으로 짜인 부분을 O(n)이나 O(log n)으로 바꿀 수 없는지 검토해 봅니다.

02.6 O(log n), 반씩 줄이면 순식간

마지막 모양은 반씩 줄여 나가는 방식입니다. 어떤 수를 1이 될 때까지 계속 반으로 나누면 몇 번 만에 끝나는지 세어 보겠습니다.

def halving(n):

steps = 0

while n > 1:

n //= 2

steps += 1

return steps

print(halving(1000))

print(halving(1000000))

9

19

1000은 9번, 100만은 19번이면 1에 닿습니다. 데이터가 1000배 늘었는데도 횟수는 겨우 두 배 남짓 늘었을 뿐입니다. 이렇게 매 단계 절반을 접어 버리는 것이 O(log n)이고, O(n)보다 훨씬 느리게 늘어 아주 빠릅니다. 정렬된 데이터에서 값을 찾는 이진 탐색이 바로 이 힘을 씁니다. 절반씩 버릴 수 있는 문제를 만나면 O(log n)을 떠올리면 됩니다. 다만 이 방법은 데이터가 미리 정렬되어 있어야 쓸 수 있다는 조건이 붙습니다.

02.7 네 가지 모양 정리

빠른 순서로 늘어놓으면 O(1), O(log n), O(n), O(n의 제곱)입니다. O(1)은 개수와 무관하게 일정하고, O(log n)은 반씩 접어 아주 느리게 늘며, O(n)은 개수에 비례하고, O(n의 제곱)은 제곱으로 폭발합니다. 코드를 짤 때 반복문이 한 겹인지 두 겹인지, 매 단계 범위가 반으로 주는지만 살펴도 대략의 모양이 보입니다. 이 눈이 생기면 돌려 보기 전에 느릴 코드를 미리 알아채고, 더 나은 자료구조나 방법으로 바꿀 수 있습니다. 빅오는 어렵게 외우는 공식이 아니라, 코드를 보는 하나의 습관이라고 생각하시면 됩니다. 같은 문제라도 어떤 자료구조와 방법을 쓰느냐에 따라 이 모양이 달라지고, 그 선택이 곧 프로그램의 속도가 됩니다. 처음에는 O(1)과 O(n)만 확실히 구분해도 충분하고, 나머지는 코드를 많이 접하며 자연스럽게 익히면 됩니다.