시간 복잡도 (Time Complexity)와 공간 복잡도 (Space Complexity)

알고리즘 성능 평가

평가하기 위해 '복잡도(Complexity)'의 척도를 사용한다. 그중 시간 복잡도와 공간 복잡도의 개념이 나오며, 동일한 기능을 수행하는 알고리즘이 있을 때 복잡도가 낮을 수록 좋은 알고리즘이라 말한다고 한다.

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

1. 시간 복잡도

시간 복잡도는 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미한다. 같은 결과를 갖는 프로그래밍 소스도 작성 방법에 따라 걸리는 시간이 달라지며, 같은 결과를 같는 소스라면 시간이 적게 걸리는 것이 좋은 소스다.

빅-오 표기법

예를 들어, 동전을 튕겨 뒷면이 나올 확률을 이야기 할 때 운이 좋으면 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배가 된다. 정렬 알고리즘 중 병합 정렬, 퀵 정렬이 대표적이다.

O(n²) (quadratic)

데이터가 많아질수록 처리시간이 급수적으로 늘어나는 알고리즘이다. 예를 들어 데이터가 10배가 되면, 처리 시간은 최대 100배가 된다. 이중 루프(n² matrix)가 대표적이며 단, m이 n보다 작을 때는 반드시 O(nm)로 표시하는 것이 바람직하다.

O(2ⁿ) (Exponential)

데이터량이 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘이다. 대표적으로 피보나치 수열이 있으며, 재귀가 역기능을 할 경우도 해당된다. 그래프와 위 설명을 참고하여, 시간 복잡도에 따른 성능을 비교하면 아래와 같다.

faster O(1) < O(log n) < O(nlog n) < O(n²) < O(2ⁿ) slower

시간 측정 방법

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

# 프로그램 소스코드
end_time = time.time() # 측정 종료
print("time:", end_time - start_time) # 수행 시간 출력

수행 시간 비교

아래의 코드는 배열에 1~100까지의 정수를 무작위로 골라 10,000개의 정수를 삽입하는데, 가장 작은 원소의 인덱스부터 차곡차곡 넣어주는 for문을 직접 짠 코드와 파이썬 기본 라이브러리 sort를 사용하여 수행 시간 차이를 보는 코드.

from random import randint
import time

# 배열에 10,000개의 정수를 삽입
array = []
for _ in range(10000):
    array.append(randint(1, 100)) # 1부터 100 사이의 랜덤한 정수

# 선택 정렬 프로그램 성능 측정
start_time = time.time()

# 선택 정렬 프로그램 소스코드
for i in range(len(array)):
    min_index = i # 가장 작은 원소의 인덱스
    for j in range(i + 1, len(array)):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i] # 스와프

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

# 배열을 다시 무작위 데이터로 초기화
array = []
for _ in range(10000):
    array.append(randint(1, 100)) # 1부터 100 사이의 랜덤한 정수

# 기본 정렬 라이브러리 성능 측정
start_time = time.time()

# 기본 정렬 라이브러리 사용
array.sort()

end_time = time.time() # 측정 종료
print("기본 정렬 라이브러리 성능 측정:", end_time - start_time) # 수행 시간 출력

해당 코드를 실행해보면

선택 정렬 성능 측정: 6.268864870071411
기본 정렬 라이브러리 성능 측정: 0.0009975433349609375

2. 공간 복잡도

공간 복잡도(Space Complexity)란 작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하느냐를 분석하는 방법.

하지만 예전에 비해 컴퓨터 성능의 발달로 인해 메모리 공간이 넘쳐나다 보니 중요도는 떨어졌다고 한다.

• 시간과 공간은 반비례적 경향이 있음
• 최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선
• 알고리즘은 시간 복잡도가 중심

공간복잡도 계산법(빅-오)

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)이 된다.

공간 복잡도를 줄이는 방법

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

프로그램에 필요한 공간은 크게

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

시간적인 측면을 무시하고 공간 복잡도만 고려한다면 고정 공간보다는 가변 공간을 사용할 수 있는 자료 구조가 더 효율적이다. 함수 호출시 할당되는 지역변수들이나 동적 할당되는 객체들도 모두 공간이 필요하다. 

 

출처 : https://velog.io/@cha-suyeon/Algorithm-시간-복잡도-공간-복잡도