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

좋은 알고리즘이란 무엇일까? 당연히 작은 메모리 공간을 차지하면서 적은 시간 내에 주어진 임무를 제대로 수행하는 알고리즘이 좋은 알고리즘이다. 알고리즘을 평가할 때 수행시간과 메모리 사용량을 평가기준으로 두는데, 이 각각에 해당하는 사항이 시간 복잡도 (time complexity) 와 공간 복잡도 (space complexity) 이다.

 

시간 복잡도란, 알고리즘의 수행시간의 분석 결과이며, 공간 복잡도란 알고리즘의 메모리 사용량에 대한 분석 결과이다.

 

시간 복잡도의 계산

알고리즘의 시간 복잡도는 연산의 횟수를 세고 처리해야 할 데이터의 수 n에 대한 연산횟수의 함수 T(n) 을 만들어서 계산한다.

 

연산 횟수의 카운팅에는 3가지 경우가 있다.

1. 최선의 경우 (Best Case)
2. 최악의 경우 (Worst Case)
3. 평균적인 경우 (Average Case)

알고리즘이 복잡해질 수록 평균적 경우는 구하기 어려워진다. 따라서 보통 알고리즘의 성능은 최악의 경우로 파악한다.

 

Elementary Operation

Program Step에서 Elementary Operation이란 프로그램의 진행 정도를 나타내는 기본 단위이다. Elementary Operation에는 4 가지 종류가 있다.

1. 대입연산
2. 사칙연산 (덧셈, 뺄셈, 곱셈, 나눗셈)
3. 비교구문
4. 함수 호출

알고리즘의 실행 순서를 따라가며 Elementary Operation이 일어나는 수를 측정해 보자.

 

def sum(num_list, n):
    tempSum = 0 # 대입 연산

    for num in num_list: # num_list의 수 (n번 만큼 반복)
        tempSum += num # 사칙 연산
    
    return tempSum

print(sum([1,2,3,4,5], 5))

 

위와 같은 함수가 있다고 가정해보자. 함수가 호출되면, tempSum이라는 변수에 대입 연산이 한번 일어난다 (1). 그 후, num_list를 돌아가며 num_list의 길이 (즉, n) 만큼 사칙 연산이 반복된다 (n) 따라서, 위 함수의 시간 복잡도는 n+1 이다.

 

성능 비교

여기 두 프로그램이 있다고 하자. 프로그램 1의 성능은 n^2 + n 이고, 프로그램 2의 성능은 20n이다. n의 크기가 작을 경우, 프로그램 1의 성능이 더 좋을 것이다. 그러나 n의 크기가 커지면 커질 수록, 프로그램 1의 처리 시간은 프로그램 2에 비해 훨씬 길어진다. 따라서 각 프로그램들의 성능은 n의 크기에 따라 결정되기도 한다.

 

그러나 처리해야할 데이터의 수 (n) 이 적다면, 두 프로그램 모두 좋은 성능을 낼 것이며, 별로 차이가 없을 것이다. 따라서 이 경우 문제될 것이 없다. 그러므로, n이 큰 경우의 처리가 중요하다.

 

Big O 표기법 (Big O Notation)

Big O란 연산 횟수의 함수 T(n) 의 최고차항의 차수에 O를 씌운 표기법이다. 아래와 같이 표기하면 된다.

 

빅오의 순서는 아래와 같으며, 커질 수록 연산 횟수가 더 많다는 뜻이며, 연산에 더 오랜 시간이 걸린다는 뜻이다. 화공과에서 수학을 배울 때 배우던 내용과 비슷하다.

위 표는 각 빅오에 따라서 연산 횟수가 얼마나 차이날 수 있는지 보여준다.

 

공간 복잡도

공간 복잡도 계산은 간단하다. 메모리를 얼마나 사용했는지 계산하면 된다. 공간 복잡도 역시 시간 복잡도 처럼 보통 최악의 경우 (worst case) 를 따져 빅오 노테이션으로 그 복잡도를 판단하게 된다.

 

가령 크기가 n인 배열을 입력했는데, 알고리즘이 내부에서 n * n 의 이차원 배열을 생성한다면 이 알고리즘의 공간 복잡도는 n^2 가 된다.

 

공간 복잡도는 보통 시간 복잡도보다 중요하게 생각되지 않는 경우가 많다. 그러나 빅데이터 처리를 하는 경우, 공간 복잡도가 위와 같이 커지게 된다면, 메모리에 한 번에 올라가지 않아 프로그램을 실행할 수 없는 문제가 발생할 수 있다. 이 경우, 데이터를 나눠서 처리하고 다시 합치는 방법을 사용하게 된다.

 

알고리즘 작성 시, 공간 복잡도를 아예 생각하지 않으면 위험할 수 있다. 따라서 공간 복잡도도 신경써서 작성해 주자.

출처

http://ledgku.tistory.com/33

https://feel5ny.github.io/2017/12/09/CS_01/

https://wayhome25.github.io/cs/2017/04/20/cs-26-bigO/