알고리즘 개념7 - 시간복잡도

시간복잡도

알고리즘 복잡도 계산이 필요한 이유

• 하나의 문제를 푸는 알고리즘은 다양할 수 있음.
• 다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하기 위해, 복잡도를 정의하고 계산함.

알고리즘 복잡도 계산 항목

• 시간복잡도 : 알고리즘 실행 속도
  • 주요요소 : 반복문
• 공간복잡도 : 알고리즘이 사용하는 메모리 사이즈

알고리즘 성능 표기법

Big O (빅오) 표기법 : O(N)

• 알고리즘 최악의 실행시간을 표기
• 가장 많이/일반적으로 사용함
• 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미이기 때문

Ω (오메가) 표기법 : Ω(N)

• 오메가 표기법은 알고리즘 최상의 실행 시간을 표기

Θ (세타) 표기법 : Θ(N)

• 세타 표기법은 알고리즘 평균 실행 시간을 표기