[Algorithm] 복잡도 Complexity

복잡도

복잡도는 알고리즘의 성능을 나타내는 척도이다. 동일한 기능을 수행하는 알고리즘이 있다면 복잡도가 낮을수록 좋은 알고리즘이다.

• 시간 복잡도 :  알고리즘을 위해 필요한 연산의 횟수
• 공간 복잡도 :  알고리즘을 위해 필요한 메모리의 양

일반적으로 코딩 테스트에서는 최악의 경우에 대한 연산 횟수가 중요하다. 따라서 최악의 경우의 시간 복잡도를 우선적으로 고려해야한다.

 

Cf) Memorization 메모이제이션 : 메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 방법

 

시간 복잡도와 공간 복잡도의 Trade-off

메모리를 많이 사용하는 대신에 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있다. 이때 메모리를 더 소모하는 대신에 얻을 수 있는 시간적 이점이 매우 큰 경우가 종종있다.

표기법

시간 복잡도와 공간 복잡도는 점근적 표기법을 사용하여 표현한다.

참고> 점근적 표기 정리

시간 복잡도 (Time Complexity)

시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래걸리는지를 의미한다.

시간 복잡도는 알고리즘을 위해 필요한 연산의 횟수를 말한다.
시간 복잡도에 따라서 부르는 명칭이 있는데 정리하면 아래의 표와 같다.

 

시간순으로 따지면
O( 1) < O( log N) < O(N) < O(NlogN) < O(N²) < O(N³) < O(2N) < O(N!)으로 표현할 수 있다.

 

O내부에 있는 n이 작을수록 성능이 좋은 알고리즘이다.

 

일반적으로 O(N^3)을 넘어가면 코딩테스트에서 사용하기 어려운 알고리즘이다.CPU기반의 개인 컴퓨터나 채점용 컴퓨터에서는 연산 횟수가 10억을 넘어가면 C언어를 기준으로 1보통 초 이상의 시간이 소요된다. 이때 N의 크기가 5,000이 넘는다면 10초 이상의 시간이 걸릴 수 있다. 특히 파이썬은 더 오랜 시간이 소요되고 코딩테스트에서 시간제한이 1~5초 이므로 연산 횟수가 10억을 넘어가면 오답 판정을 받을 수 있다.

 

빅오 표기법으로 표시한 시간 복잡도가 같더라도 알고리즘 내부 로직 및 차수가 낮은 항의 영향에 따라 10,000번 100,000번 등 실제 수행되는 연산의 횟수가 다를 수 있다. 예를들어 실제로 N이 작을 때 상수값이 1,000,000인 경우 이 값이 미치는 영향력이 크기 때문이다.

 

시간 제한이 1초인 문제에 대한 예시

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

 

공간 복잡도 (Space Complextiy)

공간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다.
일반적으로 코딩 테스트에서 메모리 사용량의 기준은 MB 단위로 제시된다. 코딩 테스트 문제는 대부분 다수의 데이터에 대한 효율적인 처리를 요구하기 때문에 리스트(배열)을 사용해서 풀어야한다. 컴퓨터 시스템에서 차지하는 메모리량은 컴파일러에 따라 조금씩 차이가 있지만 고전적인 프로그래밍 언어에서 정수형 자료형인 int를 기준으로 리스트 크기에 따른 메모리 사용량을 확인해보면 아래와 같다.

• int a[1000] : 4KB
• int a[1000000] : 4MB
• int a[2000][2000] : 16MB

코딩 테스트에서는 보통 메모리 사용량을 128~512MB로 제한한다. 다시 말해 일반적인 경우 데이터의 수가 1,000만 단위가 넘어가지 않도록 알고리즘을 설계해야한다.

파이썬에선 대략 100만 개의 데이터가 들어갈 수 있는 크기의 리스트를 선언하는 경우는 적다.

공간 복잡도는 알고리즘을 위해 필요한 메모리의 양을 말한다.

 

시간과 메모리 측정

• 수행 시간 측정 소스코드

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

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

 

참고자료

• 나동빈, 이것이 취업을 위한 코딩테스트다, 한빛 미디어