알고리즘 성능 평가: 시간복잡도 & 공간복잡도

알고리즘의 성능을 평가하는 요소로 복잡도 (Complexity)를 사용한다. 복잡도에는 시간복잡도와 공간복잡도가 있으며, 동일한 기능을 수행하는 알고리즘이 있을 때 복잡도가 낮을수록 좋은 알고리즘이라 한다.

• 시간복잡도 (Time Complexity) : 특정한 크기의 입력에 대한 알고리즘의 수행시간 분석
• 공간복잡도 (Space Complexity) : 특정한 크기의 입력에 대한 알고리즘의 메모리 사용량 분석

 

---

시간복잡도

빅오 표기법

최상 (Big-Ω Notation), 평균 (Big-θ Notation), 최악 (Big-O Notation)의 세 표기법 중 최악의 경우를 계산하는 방식인 빅오표기법으로 경우를 판단하여 평균과 가까운 성능을 예측하는 방식

 

O(1) (Constant)

입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘. 데이터가 얼마나 증가하든 성능에 영향을 거의 미치지 않는다.

Ex. 스택의 push/pop

 

O(log₂n) (Logarithmic)

입력 데이터의 크기가 커질수록 처리 시간이 로그(log: 지수 함수의 역함수) 만큼 짧아지는 알고리즘. 예를 들어 데이터가 10배가 되면, 처리 시간은 2배가 된다. Ex. 이진 탐색, 재귀가 순기능할 때

 

O(n) (Linear)

입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘. 예를 들어 데이터가 10배가 되면, 처리 시간도 10배가 된다.

Ex. 1차원 for문

 

O(nlog₂n) (Linear-Logarithmic)

데이터가 많아질수록 처리시간이 로그(log) 배만큼 더 늘어나는 알고리즘. 예를 들어 데이터가 10배가 되면, 처리 시간은 약 20배가 된다.

Ex. 병합 정렬, 퀵 정렬, 힙 정렬

 

O(n²) (quadratic)

데이터가 많아질수록 처리시간이 급수적으로 늘어나는 알고리즘. 예를 들어 데이터가 10배가 되면, 처리 시간은 최대 100배가 된다.

Ex. 2차원 for문 (단, n과 m이 다를 때는 O(nm)로 표기), 삽입 정렬, 거품 정렬, 선택 정렬

 

O(2ⁿ) (Exponential)

데이터량이 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘.

Ex. 피보나치 수열, 재귀가 역기능할 때

 

성능비교

O(1) < O(log₂n) < O(nlog₂n) < O(n²) < O(2ⁿ)

 

 

---

 

시간 측정하기 with Python

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

# 프로그램 소스코드

end_time = time.time() # 측정 종료
print("time:", end_time - start_time) # 수행 시간 출력

 

 

공간복잡도

시간복잡도와 공간복잡도는 반비례적 경향이 있으며, 최근 대용량 시스템이 보편화되며 공간복잡도보다는 시간복잡도가 우선시되고 있다.

 

 

공간복잡도를 줄이는 방법

공간복잡도를 결정하는 것은 보통 배열의 크기가 몇인지, 얼마 만큼의 동적할당인지, 몇 번의 호출을 하는 재귀함수인지 등이 공간복잡도에 영향을 끼친다. 프로그램에 필요한 공간은 크게

1. 고정 공간
2. 가변 공간

이 있는데 시간적인 측면을 무시하고 공간복잡도만 고려한다면 고정공간보다는 가변공간을 사용할 수 있는 자료구조가 더 효율적이다. 함수호출 시 할당되는 지역변수들이나 동적할당되는 객체들도 모두 공간이 필요하다. 특히, 재귀 함수의 경우 매 함수 호출마다 함수의 매개변수, 지역변수, 함수의 복귀주소를 저장할 공간이 필요해서 재귀적으로 짤 수도 있고, 반복문으로도 짤 수 있는 경우에는 반복문으로 짜는 것이 더 효율적이다.