[Algorithm] 알고리즘 복잡도 : 시간 복잡도 / Big-O (빅 오) 표기법

알고리즘 복잡도 ?

하나의 문제를 푸는 알고리즘은 다양할 수 있음
=> 어느 알고리즘이 더 좋은지를 분석하기 위해, 복잡도 계산 필요

1. 시간 복잡도 : 알고리즘 실행 속도 (반복문이 수행시간 지배)
2. 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈

 

알고리즘 성능 표기법

 

• Big O (빅-오) 표기법 : O(N)
  • 알고리즘 최악의 실행 시간을 표기
  • 가장 많이/일반적으로 사용함
  • 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미
  • O(입력) : 입력n에 따라 결정되는 시간 복잡도 함수 -> n의 크기에 따라 기하급수적으로 시간 복잡도 늘어날 수 있음
• Ω (오메가) 표기법 : Ω(N)
  • 알고리즘 최상의 실행 시간을 표기
• Θ (세타) 표기법  : Θ(N)
  • 알고리즘 평균 실행 시간을 표기