복잡도

복잡도는 알고리즘의 성능을 나타내는 척도이다. 복잡도는 시간 복잡도와 공간 복잡도로 나눌 수 있다.

 

시간 복잡도

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

일반적으로 코딩테스트 환경에서 O(n3)을 넘어가면 문제 풀이에서 사용하기 어렵다

(c 기준 n의 크기가 5000이 넘어가면 10초 이상의 시간 소요)

 

다음은 모두 시간 제한이 1초인 문제에 대한 예시이다.

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

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

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

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

-> N의 범위와 시간제한을 확인하고 문제를 설계하자. 대략 2천만번에 1초가 소요된다고 가정

 

공간 복잡도

특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다.

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

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

 

시간 측정

파이썬에서 메모리 측정은 다음과 같다.

```

import time

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

 

# 프로그램 소스코드

end_tiime=time.time() # 측정 종료

print("time : ", end_time - start_time) # 수행 시간 출력

```

tip : 파이썬의 기본 정렬 라이브러리(array.sort())는 최악의 경우 O(nlogn)을 보장하여 선택정렬(O(n2))에 비해 상대적으로 빠르다.