복잡도

복잡도는 시간 복잡도와 공간 복잡도로 나뉜다.

 

시간 복잡도는 '문제를 해결하는 데 걸리는 시간과 입력의 함수 관계'를 의미하며, 어떠한 알고리즘의 로직이 구현되는 데 걸리는 시간을 나타내는데 쓰인다. 주로 빅오 표기법으로 나타낸다. 

 

 

만일 O(n^2)의 시간 복잡도를 가지고 9초가 걸린다면, O(n)의 시간 복잡도를 가지는 알고리즘으로 개선하면 3초가 걸린다. 시간 복잡도의그래프를 보며 효율적으로 알고리즘을 개선할 수 있도록 지향해야 한다.

 

공간 복잡도는 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양을 의미한다. 즉 메모리 사용량을 의미한다.