[1주1장 CS] 알고리즘의 성능을 어떻게 표현할까? : Big-O 표기법

서론

이번 주의 주제, “알고리즘의 성능을 어떻게 표현할까?”입니다.

알고리즘의 복잡도

알고리즘은 어떤 문제를 해결하기 위한 일련의 절차와 방법입니다. 같은 문제라도 어떻게 푸는지에 따라 복잡도가 달라집니다.

알고리즘의 복잡도는 크게 시간 복잡도[Time Complexity]와 공간 복잡도[Space Complexity]로 나눌 수 있습니다[1]. 아래에서 두 복잡도를 알아보겠습니다.

시간 복잡도

예시를 들기 위해 1부터 $n$까지의 합을 구하는 코드를 작성해 보겠습니다.

# 방법 1, 전부 더하기
n = int(input())

sum = 0
for i in range(1, n + 1):
    sum += i
print(sum)

# 방법 1, 전부 더하기
n = int(input())

sum = 0
for i in range(1, n + 1):
    sum += i
print(sum)

그런데 혹시 가우스의 일화를 알고 계신가요? 가우스는 아홉살 때 1부터 100까지의 합을 구하는 문제를 받았습니다. 가우스는 맨 앞과 맨 끝을 더하면 $1+100=101$, 2번째와 뒤에서 2번째를 더하면 $2+99=101$, $\cdots$와 같은 쌍이 개수의 절반인 50쌍 나온다는 것을 생각해냈습니다. 그리고 암산으로 합이 $50\cdot101=5050$임을 구해냈죠[2]. 이 방법을 코드로 작성해 볼까요?

# 방법 2, 가우스의 방법
n = int(input())

sum = n * (n + 1) // 2 # (n + 1) * (n / 2.0)와 수학적으로는 같지만, n이 홀수일 때도 정수로 바로 나타낼 수 있습니다.
print(sum)

# 방법 2, 가우스의 방법
n = int(input())

sum = n * (n + 1) // 2 # (n + 1) * (n / 2.0)와 수학적으로는 같지만, n이 홀수일 때도 정수로 바로 나타낼 수 있습니다.
print(sum)

두 방법을 비교해 봅시다. 먼저 $n$에 따라 각 줄의 연산 횟수를 세어 봅시다.

방법 1

방법 2

실제 실행 시간도 비교해 보겠습니다. 숫자는 컴퓨터마다 다를 수 있습니다.

입력에 따른 알고리즘의 실행에 걸리는 시간을 우리는 알고리즘의 시간 복잡도라고 부릅니다[1]. 이 상황에서는 방법 1의 시간 복잡도는 선형적으로 증가하는 반면 방법 2는 상수 시간 복잡도를 가지므로, $n$이 커질수록 방법 2의 시간 복잡도가 더 낮다고 할 수 있습니다.

공간 복잡도

이번에는 다른 예시를 통해 공간 복잡도를 알아보겠습니다. 1부터 $n$까지의 수를 출력해 보겠습니다.

# 방법 1, 리스트에 저장하고 출력하기
n = int(input())

nums = [i for i in range(1, n + 1)] # 리스트에 저장

print(nums) # 리스트 출력

# 방법 1, 리스트에 저장하고 출력하기
n = int(input())

nums = [i for i in range(1, n + 1)] # 리스트에 저장

print(nums) # 리스트 출력

# 방법 2, 바로 출력하기
n = int(input())

for i in range(1, n + 1):
    print(i) # 바로 출력

# 방법 2, 바로 출력하기
n = int(input())

for i in range(1, n + 1):
    print(i) # 바로 출력

입력인 $n$을 제외하고 메모리 사용량을 생각해 봅시다. 방법 1은 리스트에 $n$개의 정수를 저장해야 하므로 $n\cdot28$ 바이트의 메모리를 사용합니다(Python은 정수에 기본 28바이트를 사용합니다)[3]. 반면 방법 2는 $n$이 커져도 메모리 사용량은 $i$ 하나, 상수만큼의 메모리만 사용할 것입니다.

입력에 따른 알고리즘의 메모리 사용량을 알고리즘의 공간 복잡도라고 부릅니다[1]. 이 상황에서는 방법 1의 공간 복잡도는 선형적으로 증가하는 반면 방법 2는 상수 공간 복잡도를 가지므로, $n$이 커질수록 방법 2의 공간 복잡도가 더 낮다고 할 수 있습니다.

Big-O 표기법

알고리즘의 복잡도를 표현할 때는 점근 표기법, 그 중에서도 Big-O 표기법이 주로 쓰입니다[4]. Big-O 표기법은 점근 표기법 중 어떤 함수의 상한을 나타내는 표기법입니다. 여기서는 그 정확한 정의보다는 그 용례에 집중하겠습니다.

점근 표기법에서는 최고차항 외에는 무시할 수 있습니다. 점근 표기법은 n이 충분히 클 때의 성질을 나타내고자 하고 정확한 값을 표기하기보다는 그 변화율에 집중합니다. 예를 들어 어떤 알고리즘이 실행에 $2n+1000$의 시간이 걸린다면, $O(n)$으로 표기합니다. n이 충분히 커진다면 $1000$이 주는 영향은 무시할 수 있는 수준이기 때문입니다. 계수 또한 생략합니다. 예를 들어 $0.0001n^2$와 같은 경우는 $O(n^2)$로 표기합니다. 계수 또한 $n$이 충분히 커지면 차수에 비해 무시할 수 있는 수준이기 때문입니다. 이런 예시에서 알 수 있듯 Big-O와 같은 점근 표기법은 정확한 시간을 표기하기보다는 입력이 커질 때의 성질을 나타내고, 비교하기 위한 용도로 사용합니다.

앞서 살펴본 1부터 $n$까지의 합을 구하는 두 방법의 시간 복잡도를 Big-O 표기법으로 나타내 봅시다. 방법 1은 실행 횟수의 합이 $2n+1$입니다. 반면 방법 2는 실행 횟수의 합이 $1$입니다(계산은 무시하겠습니다). 따라서 방법 1의 시간 복잡도는 $O(n)$ (선형), 방법 2의 시간 복잡도는 $O(1)$ (상수)입니다. 실제 실행 시간을 같이 확인해 봅시다. 방법 1에서는 $n$이 10배 늘어나는 동안 실행 시간도 비슷한 비율로 늘어났습니다^[*1] 방법 2에서는 $n$이 10배 늘어나도 실행 시간은 거의 변하지 않았습니다.

공간 복잡도도 Big-O 표기법으로 나타낼 수 있습니다. 1부터 $n$까지의 숫자를 출력하는 예시에서 방법 1은 $O(n)$, 방법 2는 $O(1)$입니다. 방법 1은 리스트에 $n$개의 정수를 저장해야 하므로 $O(n)$의 공간을 사용합니다. 반면 방법 2는 상수만큼의 공간을 사용하므로 $O(1)$입니다. 한편, 공간 복잡도는 일반적으로 시간 복잡도보다 덜 중요하게 여겨집니다. 공간 복잡도가 시간 복잡도를 넘을 수는 없고, 주로 공간 복잡도를 희생하더라도 시간 복잡도를 줄이는 방식으로 알고리즘이 설계됩니다.

한편 현실의 프로그램에서는 Big-O 표기법으로 나타나지 않는 최적화도 중요합니다. 간단한 예시를 들자면, 실행 횟수가 $1000n$인 코드와 $10n$인 코드는 둘 다 시간 복잡도가 $O(n)$으로 표기되지만 실제 실행 시간은 후자가 100배입니다. 다른 예시로, 실행 횟수가 $1000n$인 코드와 $n^2$인 코드는 각각 $O(n)$과 $O(n^2)$로 표기되지만, $0\leq{n}<1000$인 경우에는 후자가 더 빠릅니다. 이처럼 알고리즘 분야에서는 Big-O 표기법이 충분히 유용하지만, 실제 코드의 성능을 완전히 대변할 수는 없습니다.

자주 쓰이는 형태

• $O(1)$: 상수 시간 복잡도. 입력 크기에 상관없이 일정한 시간이 걸립니다. 맵의 조회, 리스트의 인덱스 접근 등이 있습니다.
• $O(\log n)$: 로그 시간 복잡도. 주로 이진 로그를 의미하지만, Big-O 표기법에서는 로그의 밑은 무시될 수 있습니다. 이진 탐색 등이 있습니다.
• $O(n)$: 선형 시간 복잡도. 입력 크기에 비례하여 시간이 걸립니다. 리스트의 순회 등이 있습니다.
• $O(n \log n)$: 선형 로그 시간 복잡도. 주로 정렬 알고리즘에서 나타납니다. 퀵 정렬, 병합 정렬 등이 있습니다.
• $O(n^c)$: 다항 시간 복잡도. $c$는 상수입니다. $c$중 for문 같은 형태일 수 있습니다.
• $O(c^n)$: 지수 시간 복잡도. $c$는 상수입니다. 피보나치 수열을 재귀로 구하는 경우가 있습니다.
• $O(n!)$: 팩토리얼[Factorial; 1부터 n까지의 자연수의 곱] 시간 복잡도. 일반적으로 가장 비효율적인 알고리즘입니다. 브루트 포스[Brute Force; 무차별 대입법] 알고리즘이 여기에 해당합니다.

정리

• 알고리즘의 복잡도: 시간 복잡도, 공간 복잡도[1]
  • 시간 복잡도: 입력 크기에 따른 실행 시간
  • 공간 복잡도: 입력 크기에 따른 메모리 사용량
• Big-O 표기법: 점근 표기법 중 상한을 나타내는 표기법[4]
  • $O(f(n))$ 꼴로 표기
  • 최고차항 사용, 계수 생략 → 변화율에 집중(점근적)
  • 알고리즘 성능 비교에 주로 사용
• 실제 코드 성능은 여러 부분이 고려되어야 함

용어

label

시간 복잡도

Time Complexity

label

공간 복잡도

Space Complexity

label

팩토리얼

Factorial; 1부터 n까지의 자연수의 곱

label

브루트 포스

Brute Force; 무차별 대입법

@misc{devngho202520250412weeklycsbigonotation,
  author       = {Yu, Dongho},
  title        = {알고리즘의 성능을 어떻게 표현할까? : Big-O 표기법},
  howpublished = {\url{https://ngho.dev/posts/20250412-weekly-cs-big-o-notation}},
  year         = {2025},
  month        = {apr},
  note         = {Accessed: 2025-05-04}
}

@misc{devngho202520250412weeklycsbigonotation,
  author       = {Yu, Dongho},
  title        = {알고리즘의 성능을 어떻게 표현할까? : Big-O 표기법},
  howpublished = {\url{https://ngho.dev/posts/20250412-weekly-cs-big-o-notation}},
  year         = {2025},
  month        = {apr},
  note         = {Accessed: 2025-05-04}
}