시간 복잡도, 공간 복잡도

알고리즘 성능 평가

 

알고리즘 성능을 평가하기 위해 '복잡도(Complexity)'의 척도를 사용한다.

 

그 중 시간 복잡도와 공간 복잡도의 개념이 나오며, 동일한 기능을 수행하는 알고리즘이 있을 때 복잡도가 낮을 수록 좋은 알고리즘이라 말한다.

 

• 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
• 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

 

1. 시간 복잡도

시간 복잡도는 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미한다. 같은 결과를 갖는 프로그래밍 소스도 작성 방법에 따라 걸리는 시간이 달라지며, 같은 결과를 같은 소스라면 시간이 적게 걸리는 것이 좋은 소스이다.

**

시간복잡도란 입력크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간이며 주요로직의 반복횟수를 중점으로 측정됩니다.

시간복잡도를 설명할 때는 시간이 아니라 어떠한 알고리즘이 주어진 입력크기를 기반으로 어떠한 로직이 몇번 반복되었는가를 중점으로 설명합니다.

 

2. 공간 복잡도

공간복잡도는 '입력크기에 대해 어떠한 알고리즘이 실행되는데 필요한 메모리 공간의 양'을 가리킵니다.

이는 정적변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함하며 배열이든 맵이든 셋이든 요소들을 담을 공간이며 다 적용됩니다.

 

공간 복잡도(Space Complexity)란 작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하느냐를 분석하는 방법이다.

 

하지만 예전에 비해 컴퓨터 성능의 발달로 인해 메모리 공간이 넘쳐나다 보니 중요도는 떨어졌다고 한다.

 

시간 복잡도의 경우 알고리즘을 잘못 구성하면 결과값이 나오지 않거나 너무 느린 속도로 나와서 최근에는 시간 복잡도를 더 우선시하여 프로그래밍을 한다.

 

정리하자면

• 시간과 공간은 반비례적 경향이 있음
• 최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선
• 알고리즘은 시간 복잡도가 중심

 

 

https://velog.io/@cha-suyeon/Algorithm-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84-%EA%B3%B5%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84

[Algorithm] 시간 복잡도, 공간 복잡도