자료구조 및 알고리즘 <시간복잡도>

---

시간복잡도 

- 알고리즘의 성능을 평가하는 척도. 입력 데이터의 크기가 커짐에 따라 알고리즘의 실행 시간이 얼마나 증가하는지를 수학적으로 표현하는 방법

표기법

- 빅-오메가 ( Big-Ω ) : 최선일 때(Best-Case)의 연산 횟수를 나타낸 표기법

- 빅-세타 ( Big-θ ) : 보통일 때(Average-Case)의 연산 횟수를 나타낸 표기법

- 빅-오( Big-O ) : 최악일 때의(Worst-case)의 연산 횟수를 나타낸 표기

---

연산 횟수 계산법

연산횟수 = 알고리즘 시간복잡도 x 데이터의 크기

시간 복잡도 도출 기준

A. 상수는 시간 복잡도 계산에서 제외한다.

B. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.