[알고리즘] 시간 복잡도, 공간 복잡도, 빅오 표기법

🚀 복잡도란?

• 알고리즘의 성능, 효율성을 나타내는 척도로 시간 복잡도와 공간 복잡도로 나눌 수 있다.
• 복잡도를 나타내는 방법으로는 점근 표기법으로 O(빅오), Ω(오메가), Θ(세타) 등이 있고, 주로 빅오와 세타 표기법이 많이 사용된다.

 

🚀 빅오 표기법

• 알고리즘을 성능을 수학적으로 표기해주는 표기법
• 복잡도를 나타내는 점근 표기법 중 가장 많이 사용되는 표기법
• 시간과 공간 복잡도를 표현할 수 있다.
• N: input size 

 

🚀 시간 복잡도(time complexity)

• 알고리즘의 입력 크기에 따라 실행 시간이 어떻게 변화하는지를 나타낸다.
• 일반적으로 Big-O 표기법을 사용하여 표현
  • Big-O 표기법은 알고리즘의 최악의 경우를 기준으로 성능을 나타내기 때문
• 시간 복잡도를 분석할 때는 알고리즘의 각 단계에서 수행되는 기본 연산의 횟수를 계산한다.
• 이를 통해 알고리즘의 전체 실행 시간을 예측할 수 있으며, 이는 알고리즘의 효율성을 평가하는 데 중요한 기준이 된다.
• 시간 복잡도를 최적화하는 것은 알고리즘의 성능을 향상시키는 데 중요한 역할을 한다. 이를 통해 더 빠르고 효율적인 알고리즘을 설계할 수 있다.

 

🚀 공간 복잡도

• 프로그램 실행과 완료에 얼마나 많은 공간(메모리)가 필요한지를 나타낸다.
• 알고리즘의 입력 크기와 처리 과정에서 사용되는 추가적인 메모리 공간을 고려하여 평가된다.
• 알고리즘의 메모리 효율성을 평가하는 데 사용되며, 메모리 사용량을 최소화하는 것은 특히 메모리 자원이 제한적인 환경에서 중요하다.
• 공간 복잡도 역시 Big-O 표기법을 사용하여 표현할 수 있으며, 예를 들어 O(N)은 알고리즘의 메모리 사용량이 입력 크기 N에 비례하여 증가함을 의미한다.

 

 

 

ℹ️ 출처

https://velog.io/@welloff_jj/Complexity-and-Big-O-notation

https://f-lab.kr/insight/understanding-time-and-space-complexity