복잡도

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

 

1. 시간 복잡도 
   : 알고리즘을 위해 필요한 연산의 횟수. 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미
2. 공간 복잡도
   : 알고리즘을 위해 필요한 메모리의 양

 

시간 복잡도

알고리즘 문제를 풀 때 단순히 복잡도라고 하면 보통은 시작 복잡도를 의미. 시간 복잡도를 표현할 때는 빅오(Big-O) 표기법을 사용한다.

 

시간 복잡도 분석은 문제 풀이의 핵심이다.

 

공간 복잡도

시간 복잡도와 마찬가지로 빅오 표기법을 사용. 

코딩 테스트 문제는 대부분 리스트(배열)을 사용해서 풀어야 한다. 고전적인 프로그래밍 언어에서 정수형 자료형인 int(4 Byte)를 기준으로 리스트 크기에 따른 메모리 용량을 확인해보면

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

코딩 테스트에서는 보통 메모리 사용량을 128~512MB로 제한함. -> 일반적인 경우 데이터 개수가 1,000만 단위가 넘어가지 않도록 알고리즘을 설계해야 한다. 만약 리스트 크기가 1,000만 단위 이상이라면 자신이 알고리즘을 잘못 설계한 것이 아닌지 고민해봐야 한다.

 

 

 

 

출처

이것이 취업을 위한 코딩 테스트나 with 파이썬 도서