알고리즘: 시간 복잡도와 공간복잡도

알고리즘을 계산하는 복잡도의 척도로는 시간 복잡도(속도)와 공간 복잡도(공간)가 있다.

현대에 들어서 대용량 시스템이 쉽게 구축됨에 따라서, 시간 복잡도 개념이 더 중요해졌다.

 

실무에서 개발자들이 시간 복잡도를 고려하는 것은 매우 중요한 이슈이다.

구성된 알고리즘에 따라 소프트웨어를 실행하는데 수 초가 차이 날 수 있으며,

단 몇 초의 차이만으로 사용자들이 어느 소프트웨어를 사용하는데 느끼는 만족도는 크게 달라질 수 있기 때문이다.

 

시간과 공간은 반비례적 경향이 있다. 그래서 공간을 희생해서라도 시간 복잡도를 낮추는 것이 많이 요구된다.

프로그램 성능을 크게 향상시켜 사용자를 만족시키는 편이 좋을 것이다.

 

 

시간 복잡도

프로그램의 성능을 분석하는 방법 중 하나이다.

시간 복잡도란, 작성된 알고리즘이 어떤 연산(문제)을 해결하는데 걸리는 수행 시간의 상관관계를 나타내는 개념이다.

즉, 알고리즘을 어떻게 구성하느냐에 따라 프로그램이 작업을 실행하는데 요구되는 시간이 달라질 수 있다.

물론 시간이 적게 요구되는 알고리즘이 더 효율적일 것이다. 

 

알고리즘을 수행하는 데 연산이 몇 번 실행되는지 숫자로 표기할 수 있다. 이때 알고리즘의 절대적인 실행 시간을 나타내는 것은 아니다.

 

공간 복잡도

프로그램의 성능을 분석하는 방법 중 하나로 공간복잡도란 개념이 사용된다.

공간 복잡도란, 작성한 프로그램을 실행한 후 그 작업을 완료하는 데 필요한 자원 공간의 양을 분석하는 방법이다. 

저장하는 데이터의 양이 1개 공간을 사용한다고 계산하면 된다.

 

간단히 말해 얼마나 많은 저장 공간(메모리)이 필요한지 계산하는 척도이다.