알고리즘[Algorithm] | 알고리즘 복잡도

복잡도

1. 시간 복잡도: 특정한 크기의 입력에 대해 알고리즘이 얼마나 오래 걸리는지 의미
2. 공간 복잡도: 특정한 크기의 입력에 대해 알고리즘이 얼마나 많은 메모리를 차지하는지 의미

동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘

 

시간 복잡도

빅오(Big-O)표기법을 사용

a = 5
b = 7
print(a + b)

위 소스코드의 연산 횟수는 1이므로 시간 복잡도는 상수 시간인 O(1)이 된다.

 

array = [3, 4, 5, 6]
summary = 0

for x in array:
  summary += x

print(summary)

위 소스코드는 4개의 데이터를 차례로 4번 더해준다.

즉, 연산 횟수는 N개의 데이터에 비례함으로 시간 복잡도는 선형 시간인 O(N)이 된다.

 

array = [3, 4, 5, 6]

for i in array:
  for j in array:
    result = i * j
    print(result)

위 소스코드는 2중 반복문을 이용하여 모든 원소끼리 곱한 결과를 출력하고 있다.

연산 횟수는 N * N 이므로 시간 복잡도는 이차 시간인 O(N^2)이 된다.

 

공간 복잡도

빅오(Big-O)표기법을 사용하며 메모리 사용량 기준은 MB단위로 제시된다.

 

시간 측정하는 방법

파이썬의 내장 모듈인 time 라이브러리를 사용하여 수행 시간을 측정할 수 있다.

import time

# 측정 시작
start_time = time.time()

# ~ 프로그램 소스코드 ~

#측정 종료
end_time = time.time()

# 수행 시간 출력
print("time: ", end_time - start_time)