[Algorithm] 시간 복잡도, 공간 복잡도

미남잉·2021년 11월 3일

algorithm datastructure python

당분간 제 교수님이 되실 '나동빈'님입니다! 아주아주 유명하신 분이죠. 코딩 테스트 스터디에 참여하여 해당 교재로 공부하게 되었고, 복습하고 정리할 수 있는 부분을 정리해보려고 합니다.🧐

시청 강의

1. 코딩 테스트 출제 경향 분석 및 파이썬 문법 부수기

오늘은

1강: 코딩 테스트 개요 및 출제 경향 00:00:00
2강: 알고리즘 성능 평가 00:16:24

이 파트를 같이 시청했고 2강의 경우는 시청 후에 간단히 이야기를 나누며 내용을 한 번 더 이해하는 시간을 가졌습니다.

이번 강의는 무려 2시간 20분짜리인데, 뒷파트는 파이썬 문법 파트로 이루어져 있습니다! 시작 전 복습하면 좋을 것 같네요.

알고리즘 성능 평가

어떤 알고리즘이 있을 때, 그 알고리즘의 성능 평가는 어떻게 할 수 있을까요?

알고리즘 성능을 평가하기 위해 '복잡도(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

slower로 갈수록(즉, 오른쪽 방향으로 갈수록) 효율성이 떨어집니다.

빅오 표기법 예제

O(1) : 스택의 Push, Pop
O(log n) : 이진트리
O(n) : for 문
O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)
O(n²): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
O(2ⁿ) : 피보나치 수열

시간 측정 방법

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

엄청나게 시간이 차이가 발생합니다. 보통 코딩 테스트 문제를 풀 때 수행 시간으로 1~5초를 준다고 하니까 6초가 걸리는 방식으로 코드를 짜면 안 된다는 걸 알 수 있습니다.

다시 시도했을 경우,

선택 정렬 성능 측정: 4.549175024032593
기본 정렬 라이브러리 성능 측정: 0.000997304916381836

어쨌든 성능 차이가 큽니다.

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

공간 복잡도를 줄이는 방법

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

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

고정 공간
가변 공간

이 있는데, 시간적인 측면을 무시하고 공간 복잡도만 고려한다면 고정 공간보다는 가변 공간을 사용할 수 있는 자료 구조가 더 효율적입니다.

함수 호출시 할당되는 지역변수들이나 동적 할당되는 객체들도 모두 공간이 필요합니다. 특히, 재귀 함수의 경우 매 함수 호출마다 함수의 매개변수, 지역변수, 함수의 복귀 주소를 저장할 공간이 필요해서 재귀적(Recursive)으로 짤 수도 있고, 반복문으로도 짤 수 있는 경우에는 반복문으로 짜는 것이 더 효율적이라 봅니다.