[자료구조] Big-O (빅오)

소프트웨어 내 저마다의 알고리즘이 있을텐데, 동일한 기능을 수행하는 알고리즘이라도 어떻게 코딩을 했는지에 따라 성능은 천차만별일 것 입니다. 그렇다면 성능을 어떻게 평가 할까요?

 

요구사항이나 제약 조건에 따라 다르겠지만, 주로 시간복잡도(Time Complexity), 공간복잡도(Space Complexity)를 통해서 성능을 평가할 것 입니다.

 

이렇듯 '알고리즘 실행에 얼마나 걸리는지',  '사용하는 메모리 양이 얼마나 되는지를' 나타내는 지표는 "가장 효율적으로 문제를 해결하는 알고리즘"을 의미하기도 합니다.

 

 

1. 시간 복잡도를 표현하는 방법은 무엇이 있을까요?

 

가장 많이 사용하는 표기법이 바로 Big-O 표기법이라고 합니다. 어떤 프로그램의 연산 횟수가 f(x)라고 할 때, 함수의 최고차항을 남기고 차수를 지워 O로 표기하는 것 입니다.

 

아래 그래프를 보면 이해가 되실텐데, x축은 입력 크기(N)로 알고리즘이 처리해야 하는 데이터의 개수를 의미하고, y축은 연산횟수, 실행시간을 의미한다고 보시면 됩니다. 즉, 데이터 크기에 따라 실행시간이 얼마나 걸리는지를 표현한 것 입니다.

 

 

 

 

2. 하지만 개념적인 부분들 보다 직접 계산해서 이해해보는게 좋겠죠?

-  통상적으로 컴퓨터가 1초당 10^10회 (1억회) 연산 가능하다고 가정
-  데이터 개수는 10^5 건으로 통일하여 비교
-  알고리즘이 아닌 수학적인 연산 과정을 통해 실행시간 비교

import math
import time

com = 10**8
print('컴퓨터 초당 연산 수: ', com)

N = 10**5
print('데이터 입력 크기: ', N)

 

수학적 연산을 통한 Big-O 예상 실행시간 산정

# O(log N) - 로그 연산 (log_2(N))
def o_log_n():
   return math.log2(N)

# O(N) - 선형 연산 (1부터 N까지 합)
def o_n():
   return sum(range(N))

# O(N log N) - 선형로그 연산 (∑ log_2 i)
def o_n_log_n():
   return sum(math.log(i) for i in range(1, N))

# O(N^2) - 이차 연산 (모든 i, j 쌍의 곱)
def o_n2():
   total = 0
   for i in range(N):
      for j in range(N):
         total += i * j
   return total

# O(2^N) - 지수 연산 (2^N)
def o_2_n():
   return 2**N

# 이론적 실행 시간 계산 (연산 횟수 / 초당 연산 횟수)
def estimate_time(N):
   return N / com

print(f"O(1) 연산 횟수: 1 \t\t 예상 실행 시간: {estimate_time(1):.10f} 초")
print(f"O(logN) 연산 횟수: {math.log2(N):.2f} \t 예상 실행 시간: {estimate_time(math.log2(N)):.10f} 초")
print(f"O(N) 연산 횟수: {N} \t\t 예상 실행 시간: {estimate_time(N):.10f} 초")
print(f"O(N logN) 연산 횟수: {N * math.log2(N):.2f} \t 예상 실행 시간: {estimate_time(N * math.log2(N)):.10f} 초")
print(f"O(N^2) 연산 횟수: {N**2} \t 예상 실행 시간: {estimate_time(N**2):.2f} 초")
print(f"O(2^N) 연산 횟수: 2^100000 \t 예상 실행 시간: 10^{30092} 초 (컴퓨터 연산 불가!)")

 

연산 결과를 보면 각 실행시간이 얼마나 차이가 발생하는지 알 수 있습니다. 특히 지수 연산으로 가면 오버플로우가 발생하거나 실행이 멈출 수도 있고, 지수 시간 알고리즘(O(2^N))은 N이 조금만 커져도 사용이 불가능 합니다.

O(1) 연산 횟수: 1                             예상 실행 시간: 0.0000000100 초
O(logN) 연산 횟수: 16.61                예상 실행 시간: 0.0000001661 초
O(N) 연산 횟수: 100000                  예상 실행 시간: 0.0010000000 초
O(N logN) 연산 횟수: 1660964.05   예상 실행 시간: 0.0166096405 초
O(N^2) 연산 횟수: 10000000000     예상 실행 시간: 100.00 초
O(2^N) 연산 횟수: 2^100000           예상 실행 시간: 10^30092 초 (컴퓨터 연산 불가!)