알고리즘 성능 평가
어떤 알고리즘이 있을 때, 그 알고리즘의 성능 평가는 어떻게 할 수 있을까요?
알고리즘 성능을 평가하기 위해 '복잡도(Complexity)'라는 척도를 사용합니다.
그 중 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)의 개념이 나오며, 동일한 기능을 수행하는 알고리즘이 있을 때, 복잡도가 낮을 수록 좋은 알고리즘이라 말합니다.
- 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
- 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석
1_1. 시간 복잡도
시간 복잡도는 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미합니다.
같은 결과를 갖는 코드도 작성 방법에 따라 걸리는 시간이 달라지며, 같은 결과를 가지는 코드라면 시간이 적게 걸리는 것이 좋은 코드입니다.
왜냐하면 알고리즘을 수행하는 컴퓨터에 따라서 결과가 달라 질 수 있기 때문입니다.
컴퓨터, 언어, 프로그래머뿐만 아니라 루프 색인의 증가, 포인터의 세팅 등과 같은 모든 알고리즘 상의 복잡한 세부사항과는 독립적인 측정법이 필요합니다. 실행시간은 입력의 크기가 커지면 증가하고, 총 실행시간은 단위연산이 몇 번 수행되는가에 거의 비례하기 때문에 단위연산이 수행되는 횟수를 분석하여 알고리즘의 효율성을 분석합니다.
즉, 시간 복잡도란 입력(Input) 크기를 기준으로 단위연산을 몇 번 수행하는지 구하는 것입니다.
단위연산의 횟수를 세는 데에는 차수가 중요합니다.
복잡도 카테고리는 여러가지, 셀 수 없을 만큼 많지만 대표적인 것은 다음과 같습니다.
1, log(n), n, nlog(n), n^2, n^3, 2^n, n!
왼쪽에서 오른쪽으로 갈 수 록 시간 복잡도가 높은 것입니다.
faster:: 1 < log(n) < n < nlog(n) < n^2 < n^3 < 2^n < n! ::slower
즉, 오른쪽으로 갈수록 효율성이 떨어집니다.
빅-오 표기법(Big-O notation)
시간 복잡도에는 빅-오 표기법이라는 개념이 나옵니다.
예를 들어, 동전을 튕겨 뒷면이 나올 확률을 이야기 할 때 운이 좋으면 1번에 뒷면이 나오지만, 운이 안 좋다면 n번 만큼 동전을 튕겨야 하는 경우가 발생합니다.
이 최악의 경우를 계산하는 방식을 빅-오(Big-O) 표기법이라 부릅니다.
여기서 n이란 입력되는 데이터를 의미합니다.
O(1) (Constant)
입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 나타냅니다.
데이터가 얼마나 증가하든 성능에 영향을 거의 미치지 않습니다.
O(log₂ n) (Logarithmic)
입력 데이터의 크기가 커질수록 처리 시간이 로그(log: 지수 함수의 역함수) 만큼 짧아지는 알고리즘입니다.
예를 들어 데이터가 10배가 되면, 처리 시간은 2배가 됩니다.
이진 탐색이 대표적이며, 재귀가 순기능으로 이루어지는 경우도 해당됩니다.
O(n) (Linear)
입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘입니다.
예를 들어 데이터가 10배가 되면, 처리 시간도 10배가 됩니다.
대표적으로 1차원 for문이 있습니다.
O(n log₂ n) (Linear-Logarithmic)
데이터가 많아질수록 처리시간이 로그(log) 배만큼 더 늘어나는 알고리즘입니다.
예를 들어 데이터가 10배가 되면, 처리 시간은 약 20배가 된다.
정렬 알고리즘 중 병합 정렬(merge sort), 퀵 정렬(quick sort)이 대표적입니다.
O(n²) (quadratic)
데이터가 많아질수록 처리시간이 급수적으로 늘어나는 알고리즘입니다.
예를 들어 데이터가 10배가 되면, 처리 시간은 최대 100배가 됩니다.
이중 루프(n² matrix)가 대표적이며 단, m이 n보다 작을 때는 반드시 O(nm)로 표시하는 것이 바람직합니다.
O(2ⁿ) (Exponential)
데이터량이 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘입니다.
대표적으로 피보나치 수열이 있으며, 재귀가 역기능을 할 경우도 해당됩니다.
빅-오 표기법 예제
- O(1) : Stack의 Push, Pop
- O(log n) : 이진트리(binary tree)
- O(n) : for 문
- O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)
- O(n²): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
- O(2ⁿ) : 피보나치 수열(fibonacci sequence)
시간 측정 방법
/** 파이썬 **/
import time
start_time = time.time() # 측정 시작
# 프로그램 소스코드
end_time = time.time() # 측정 종료
print("time:", end_time - start_time) # 수행 시간 출력// 코틀린
fun main() {
val begin = System.nanoTime()
/* 코드 시작 */
// 2초간 휴면
Thread.sleep(2000)
/* 코드 끝 */
val end = System.nanoTime()
println("Elapsed time in nanoseconds: ${end-begin}")
}
1_2. 공간 복잡도
공간 복잡도란 작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하느냐를 분석하는 방법입니다.
하지만 컴퓨터 성능의 발달로 인해 메모리 공간이 넘쳐나다 보니 중요도는 떨어졌습니다.
시간 복잡도의 경우 알고리즘을 잘못 구성하면 결괏값이 나오지 않거나 너무 느린 속도로 나와서 최근에는 시간 복잡도를 더 우선시하여 프로그래밍을 작성합니다.
정리하자면
- 시간과 공간은 반비례적 경향이 있음
- 최근 대용량 메모리가 보편화되며, 공간 복잡도보다는 시간 복잡도가 우선시 됨.
- 알고리즘은 시간 복잡도가 중심
공간복잡도 계산법(빅-오)
a = 1일반적으로 공간이 하나 생성되는 것을 1이라고 표현합니다. 이를 O(1)로 표기합니다.
result = 0
for i in range(1, 100):
result += i- 반복문이 N번만큼 반복해도 for문 안에서의 지역변수이므로 공간 복잡도는 여전히 O(1)이다.
- i와 result 변수만 사용
- 다른 것은 전혀 영향을 주지 않음
여기서의 공간 복잡도도 O(1)입니다.
하지만 재귀함수일 경우에는 이야기가 달라집니다.
def factorial(n):
if n == 1: # n이 1일 때
return 1 # 1을 반환하고 재귀호출을 끝냄
return n * factorial(n - 1) # n과 factorial 함수에 n - 1을 넣어서 반환된 값을 곱함위의 경우 함수의 매개변수 n의 값에 따라 공간 복잡도가 달라지는 경우입니다.
함수 내부에서 n이 1일 때까지 팩토리얼을 구하는 함수가 재귀적으로 호출되므로 스택에는 n부터 1까지 모두 쌓이며 공간 복잡도는 O(n)이 됩니다.
공간 복잡도를 줄이는 방법
공간 복잡도를 결정하는것은 보통 배열의 크기가 몇인지, 얼마 만큼의 동적 할당인지, 몇 번의 호출을 하는 재귀 함수인지 등이 공간 복잡도에 영향을 끼칩니다.
프로그램에 필요한 공간은 크게
- 고정 공간
- 가변 공간
시간적인 측면을 무시하고 공간 복잡도만 고려한다면 고정 공간보다는 가변 공간을 사용할 수 있는 자료 구조가 더 효율적입니다.
함수 호출시 할당되는 지역변수들이나 동적 할당되는 객체들도 모두 공간이 필요합니다. 특히, 재귀 함수의 경우 매 함수 호출마다 함수의 매개변수, 지역변수, 함수의 복귀 주소를 저장할 공간이 필요해서 재귀적(Recursive)으로 짤 수도 있고, 반복문으로도 짤 수 있는 경우에는 반복문으로 짜는 것이 더 효율적이라 봅니다.
