시간 복잡도 계산하기

⏱ 시간 복잡도

> 연산의 개수를 세어 얼마만큼의 연산이 수행되는가

> O(Big-O), Ω(Omega), Θ(Theta)

> 상한 / 하한 / 평균

중요한 요소 

- 조건문 (if)
- 반복문 (for, while, foreach)
- 재귀호출

규칙

- 시간 복잡도에서 상수값은 무시
- 실제 개발자가 짜 놓은 코드를 수행하는 것은 상수 시간으로 간주

요약 

- 반복문이 중첩이 되어 있는가?

- 반복문 가장 안쪽에 있는 N의 수를 파악하자

- 반복문이 총 몇번 돌아가는지, 1/2일씩 줄어 드는지

 

🗻공간 복잡도

> 얼마나 많은 저장 공간이 필요한지

> 배열이 몇개인지, 재귀함수라면 기본적으로 O(N)

> 재귀함수 + 배열 이라면 총 배열이 몇개인지 파악하자

 

요약

- N과 상관관계가 있는지 파악하자

- 배열이 몇개 인가가 중요하다