알고리즘의 성능을 나타내는 복잡도

복잡도는 알고리즘의 성능을 나타내는 척도다. 

복잡도

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

- 공간복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지 의미 

일반적으로 복잡도가 낮을수록 좋은 알고리즘이다.

 

알고리즘 문제를 풀 때 '복잡도' 는 시간 복잡도이다. 시간 제한이 문제를 푸는 시간을 정한 듯하지만, 코딩 테스트에서는 작성한 프로그램이 모든 입력을 받아 이를 처리하고 실행 결과를 출력하는 데까지 걸리는 시간을 의미한다. 프로그램을 비효율적으로 코딩해서 시간제한을 넘긴다면 -> '시간초과' 와 함께 오답^^

 

시간복잡도를 표현할 때는 빅오 표기법을 사용한다. 

빅오 표기법 (아래로 갈수록 느림 !)	명칭
O(1)	상수 시간
O(logN)	로그 시간
O(N)	선형 시간
O(NlogN)	로그 선형 시간
O(N^2)	이차 시간
O(N^3)	삼차 시간
O(2^n)	지수 시간

코딩테스트에서 보면 '시간 제한 1초, 메모리 제한 128MB' 와 같은 문장은 시간복잡도와 공간복잡도를 함께 제한하기 위하여 명시하는 것이다. 코테는 보통 리스트 ( 배열)을 이용하여 푸는데 그 이유는 다수의 데이터에 대한 효율적인 처리를 요구하기 때문이다. 

 

import time

start_time = time.time()

#프로그램 소스코드

 

end_time = time.time()

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

 

코테에서 주로 출제 빈도가 높은 것은 그리디, 구현 , DFS/BFS 를 활용한 탐색문제다.