시간 복잡도(Time Complexity) 와 공간 복잡도(Space Complexity)

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

 

복잡도에는 시간 복잡도와 공간 복잡도가 있으며, 동일한 기능을 수행하는 알고리즘을 테스트 하는 경우에는  

복잡도가 낮을수록 좋은 알고리즘이라고 흔히들 말한다.

 

좋은 알고리즘 : 알고리즘이 수행을 시작하여 결과가 도출될 때까지 걸리는 시간이 짧고 연산하는 컴퓨터 내의 메모리와 같은 자원을 덜 사용하는 알고리즘

 

**시간 복잡도

   특정 값에 대하여 알고리즘 수행 시간을 분석

**공간 복잡도

   특정 값에 대하여 알고리즘의 데이터 사용량을 분석

 

 

1. 시간 복잡도(Time Complexity)

알고리즘의 수행 시간을 분석할때 시간 복잡도를 이용한다. 

 

시간 복잡도는 3가지로 주로 나타낸다. 

최선의 경우(Best Case), 최악의 경우(Worst Case), 평균적인 경우(Average Case)

• 최선의 경우(Best Case): 알고리즘의 수행시간이 가장 적게 걸리는 경우를 의미합니다.
• 최악의 경우(Worst Case): 알고리즘의 수행 시간이 가장 오래 걸리는 경우를 의미합니다. 
• 평균적인 경우(Average Case): 알고리즘의 모든 입력을 고려한 후, 입력이 발생하는 확률을 고려해 평균 수행시간을 구합니다,.

일반적인 경우에는 평균적인 경우를 사용 할 수도 있다라고 생각 할 수도 있지만, 알고리즘은 복잡하면 복잡해질수록 평균적인 경우를

구하기가 어려워지기 때문에 최악의 경우로 알고리즘의 성능을 파악합니다.

 

 

2. 공간 복잡도(Space Complecity)

 

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

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

 

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

 

 

 

Reference:

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

https://imsoncod.tistory.com/3