복잡도(Complexity)-시간복잡도 와 공간복잡도

복잡도(Complexity)

• 시간 복잡도(Time Complexity) : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미 (알고리즘을 위해 필요한 연산의 횟수)
• 공간 복잡도(Space Complexity) : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미 (알고리즘을 위해 필요한 메모리의 양)

 

효율적인 알고리즘을 사용한다고 했을 때, 보통 시간 복잡도와 공간 복잡도는 일종의 Trade off 관계가 성립한다. 메모리를 조금 더 많이 사용하는 대신에 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있다.

이 때, 메모리를 더 소모하는 대신에 얻을 수 있는 시간적 이점이 매우 큰 경우가 종종 있다. 실제로 메모리를 더 많이 사용함으로써 시간을 비약적으로 줄이는 방법으로 메모제이션(동적계획법) 기법이 있다.

 

※ 일반적으로는 중요도는 실행속도가 메모리 사용량보다 중요하다.

         (단순히 코딩테스트 가 아닌 다른 점에서는 메모리 사용량이 더 중요할 수도 있다)

※ 알고리즘의 성능을 판단하는 데 있어서 중요한 것은 '최악의 경우'이다.

 

시간 복잡도(Time Complexity)

    : 시간 복잡도를 표현할 때는 빅오(Big-O) 표기법을 사용한다. 빅오 표기법이란 간단히 말해, 가장 빠르게 증가하는 항만을 고려하는 표기법이다. 예를 들어, 아래와 같은 코드가 있다고 가정해보다.

array = [1,2,3,4,5]    # 5개의 데이터 (N = 5)

sum = 0    # 합계를 저장하는 변수

# 모든 데이터를 하나씩 확인하며 합계를 계산
for i in array :
    sum += i
   
# 결과를 출력
print(sum)     # 15가 출력된다.

N개의 데이터가 있을 때, 위 코드는 현재 5개의 데이터가 있기 때문에, 연산 횟수는 5이다. 물론, sum 이라는 변수에 0을 할당하는 연산도 있고, print(sum)처럼 sum을 출력하는 부분도 있지만, 이런 연산 횟수가 N에 비례하기에 N이 커짐에 따라 이러한 부분들은 무시할정도로 작아진다.

따라서, 본 소스코드에서 가장 영향력이 큰 부분은 N에 비례하는 연산을 수행하는 반복문 부분이므로, 시간 복잡도를 O(N)이라고 표기할 수 있다. 

빅-오 표기법에서는 O(2N)이나 O(3N) 등으로 표기하지 않고 다 O(N)으로 표기한다. 즉, N에 따라 비례하므로, 따로 그 앞의 상수는 무시한다.

물론, '실제 코딩 테스트'에서는 차수가 작은 항들을 완전히 무시하는 것도 곤란하다. 연산 횟수가 3n³ + 5n²+ 1000000 인 알고리즘이 있다고 하면, 빅오 표기법에서는 차수가 가장 큰 항만 남기기 때문에,  O( n³) 으로 표기되지만, 실제로 N이 작을 때는 상수값 1000000이 행사하는 영향력은 무시할 수 없기 때문에, 상수를 고려해야 하는 경우는 일반적으로 적지만, 항상 빅오표기법이 절대적인 것은 아니라는 점도 기억해놓자.

 

 

그러면, 아래와 같은 코드는 어떨까?

array = [1,2,3,4,5]    # 5개의 데이터( N = 5)

for i in array :
	for j in array :
    	temp = i * j
        print(temp)

 본 소스코드는 O(n²) 의 시간복잡도를 가진다. 2중 for문을 가지기 때문에 쉽게 N * N  만큼의 연산이 필요하다는 것을 유추할 수 있지만, 실제로 모든 2중 반복문의 복잡도가 O(n²)를 가지는 것은 아니다. 소스코드가 내부적으로 다른 함수를 호출한다면, 내부 함수의 시간 복잡도까지 고려해야 한다. 따라서 소스코드를 정확히 분석한 뒤에, 시간복잡도를 계산해야 하는 점을 기억하자.

 

다음은, 자주 등장하는 시간 복잡도 표이다.

출처: https://joshuajangblog.files.wordpress.com/2016/09/1.jpg?w=638

 

O( 1) < O( log n) < O( n) < O( n* log n ) < O( n²) < O( n³)  < O( 2n ) < O( n! ) 

순으로 표현되며, O 내부에 있는 n 계산이 작을 수록 성능은 더 좋은 것이다.

 

※ 일반적으로, 코딩 테스트 환경에서는 O( n³) 을 넘어가면 문제 풀이에서 사용하기에 어렵다. CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서는 연산 횟수가 10억을 넘어가면 C언어를 기준으로 통상 1초 이상의 시간이 소요되기 때문이다. 코딩 테스트의 문제에서 시간 제한은 1 ~ 5 초가량이므로 보통 연산 횟수가 10억을 넘어가도록 작성하면, 오답 판정을 받을 수 있다.

 

자료구조에서의 설명이 아니라 알고리즘에서의 복잡도 설명이므로, 코테를 기준으로 설명해보자면, 시간 복잡도 분석은 문제풀이의 핵심이다. 알고리즘 숙련자들은 문제를 해석하기 전에 조건을 먼저 보기도 한다. 흡사, 우리가 수학문제나 언어문제를 풀기 전에 조건이나 보기를 먼저 확인하는 것과 비슷하다. 얼마나 효율적인 알고리즘을 작성해야 하는지 조건을 통해 눈치 챌 수 있기 때문이다. 

 

다음은 모두 시간제한이 1초인 문제의 일련의 예시를 나열한 것이다.

N의 범위가 500 인 경우 : 시간 복잡도가 O( n³) 인 알고리즘을 설계하면 문제를 풀 수 있다.

N의 범위가 2000 인 경우 : 시간 복잡도가 O( n²) 인 알고리즘을 설계하면 문제를 풀 수 있다.

N의 범위가 100000 인 경우 : O(n* log n) 인 알고리즘을 설계하면 문제를 풀 수 있다.

N의 범위가 10000000 인 경우 : O( n) 인 알고리즘을 설계하면 문제를 풀 수 있다.

 

 

공간 복잡도(Space Complexity)

    : 공간 복잡도를 표기할 때도 시간 복잡도를 표기했던 것처럼 빅오 표기법을 이용한다. 다만, 코딩테스테서는 앞서 시간 복잡도에서는 1초라는 절대적인 제한이 있던 것처럼, 메모리 사용량에도 절대적인 제한이 있다. 쉽게 말해, MB(메가바이트)단위로 제시되는 메모리 사용량 기준은 공간복잡도를 제한하기 위하여 명시하는 것이다.

 

정수형 자료형인 int를 기준으로 리스트 크기에 따른 메모리 사용량을 확인해보자. 단, 실제로 컴퓨터 시스템에서 차지하는 메모리양은 컴파일러에 따라 조금씩 다르게 적용될 수 있다.

int a[1000]  // 4KB
int a[1000000]	// 4MB
int a[2000][2000]    // 16MB

코딩 테스트에서는 보통 메모리 사용량을 128~512 MB로 제한하는데, 일반적인 경우 데이터의 개수가 1000만 단위가 넘어가지 않도록 알고리즘을 설계해야 한다는 의미이다. 파이썬에는 int 자료형이 따로 없지만, 대략 100만개 이상의 데이터가 들어갈 수 있는 크기의 리스트를 선언하는 경우는 적다는 점을 기억하자.