시공간 복잡도

2021 네이버 부스트 캠프 (웹,앱) 1차 테스트에 응시하였고 나름대로 나쁘지 않게 쳤다고 생각합니다. 문제를 푸는 와중에도 재밌었던 기억이 떠올라 알고리즘 공부를 탄탄히 하고 싶어졌습니다. 그래서 시간 복잡도와 공간 복잡도 관련하여 공부한 내용입니다. (종만북을 통해 공부하였습니다.)

알고리즘

알고리즘을 평가하는 두 가지의 기준이 있습니다.

시간과 공간입니다.

• 시간 : 얼마나 더 빠르게 동작하는가?
• 공간 : 얼마나 더 적은 용량의 메모리를 사용하는가?

같은 프로그램이라 하더라도 어떤 값이 주어지냐 어떤 컴퓨터에서 실행되냐에 따라 많은 차이를 보입니다.

따라서 이를 해결하기 위해 “시간 복잡도”, “공간 복잡도”의 개념이 필요합니다.

 

시간 알고리즘

시간 알고리즘에는 크게 “선형 이하 시간 알고리즘”, “다항 시간 알고리즘”, “지수 시간 알고리즘”이 있습니다.

선형 이하 시간 알고리즘

 

선형 이하 시간 알고리즘은 일반적으로 이진 탐색이 있습니다. N개를 모두 찾는 방식이 아니라 반씩 나눠가면서 찾으면 logN형태의 시간이 걸릴 것으로 예상할 수 있습니다. log는 입력이 커지는 것 보다 느리게 증가하는 알고리즘 입니다.

다항 시간 알고리즘은 (N, N^2...) N의 거듭제곱들의 선형 결합으로 이루어진 알고리즘 입니다. 일반적으로 다항 시간 알고리즘 간에도 엄청 나게 큰 시간 차이가 날 수 있습니다.

지수 시간 알고리즘은 (2^N, 3^N ...) 등 입력 크기에 따라 비교도 다른 시간 알고리즘에 비해 비교도 안 되게 빠르게 증가합니다. 지수 시간 알고리즘이라 하더라도 무조건 비효율 적인 알고리즘은 아닙니다. 지수 시간 알고리즘보다 빠르지 않은 알고리즘이 많기 때문입니다. 그러나 일반적으로 지수 시간 알고리즘이 나오는 경우 효율적으로 해결하는 방법이 있는지 생각해볼 필요가 있습니다.

 

시간 복잡도

시간 복잡도는 가장 널리 사용되는 알고리즘의 수행 시간 기준입니다.

알고리즘이 실행되는 동안 수행하는 연산의 수를 입력의 크기에 대한 함수로 표현한 것 입니다.

시간 복잡도가 낮으면 입력의 크기가 클수록 더 효율적입니다.

일반적으로 시간복잡도는 O표기를 이용합니다. 또한 알고리즘의 수행시간에 가장 빨리 변하는 항을 계수를 떼어 남깁니다. 예를 들어 5N^2+3N인 경우 O(N^2)으로 표기합니다.

시간복잡도를 이용한 수행 시간 짐작하기

 

시간복잡도를 통해 정확하지 않지만 시간 제한 내에 문제를 풀 수 있는지 짐작할 수 있습니다.

일반적으로 1초당 반복문 수행 횟수가 1억(10^8)을 넘어가면 시간 제한을 초과할 가능성이 있습니다.

경우에 따라 달라지기 때문에 충분한 여유를 두는 것 이 좋습니다.