🤓 What I Learned Today

(참고서적)

시간복잡도와 공간복잡도

Q.
시간복잡도와 공간복잡도가 무엇인지 설명해주실 수 있을까요?

A.
알고리즘을 평가하는 지표로

시간 복잡도는 알고리즘의 수행시간을 평가하고

공간 복잡도는 알고리즘 수행에 필요한 메모리 사용량을 평가 합니다.

여기서 복잡도란 가독성와 다른 의미로 쓰입니다. 불특정한 함수의 성능적인 측면에서 복잡도를 의미합니다.동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮은 알고리즘이 좋은 알고리즘입니다.

---

추가개념❗️

시간 복잡도(Time Complexity)
(알고리즘의 수행시간을 분석할 때 시간 복잡도를 사용하는데 수행시간은 실행환경.)

왜 시간 복잡도를 쓸까?
효율적으로 코드를 개선하는 데 쓰이는 척도가 된다.

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

1. 최선의 경우 (Best Case)

   • 빅 오메가 표기법 사용
   • 최선의 시나리오로 최소 이만한 시간이 걸림

2. 최악의 경우 (Worst Case)

   • 빅 오 표기법 사용
   • 최악의 시나리오로 아무리 오래 걸려도 이 시간보다 덜 걸림

3. 평균적인 경우 (Average Case)

   • 빅 세타 표기법 사용
   • 평균 시간을 나타냄

평균적인 경우를 가장 많이 사용할 것 같지만 알고리즘이 복잡해질수록 평균적인 경우는 구하기가 매우 어려워 지기 때문에 최악의 경우로 알고리즘의 성능을 파악

공간 복잡도(Space Complexity)
(공간 복잡도는 알고리즘에서 사용하는 메모리 양)

공간 복잡도는 보조공간(Auxiliary Space)과 입력 공간(input size)을 합친 포괄적인 개념

보조 공간(Auxiliary Space)은 알고리즘이 실행되는 동안 사용하는 임시 공간이기 때문에 입력 공간(input size)을 고려하지 않고 공간 복잡도도 시간 복잡도와 유사하게 빅오 표기법을 사용