[Fast Campus] 한 번에 끝내는 코딩테스트 369 : 복잡도

✨ 알고리즘 복잡도 표현 방법

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

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

알고리즘 복잡도 계산 항목

• 시간 복잡도 : 알고리즘 실행 속도
  👉 시간 복잡도의 주요 요소는 반복문 (입력의 크기가 커지면 커질수록 반복문이 알고리즘 수행 시간을 지배)
• 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈
  👉 메모리 용량이 계속 증가함에따라 공간 복잡도 보다 일반적으로 시간 복잡도가 복잡도의 기준

알고리즘 성능 표기법

• Big O (빅-오) 표기법: O(N)
  • 최악의 실행 시간을 표기
  • 가장 많이 일반적으로 사용
  • 아무리 최악의 상황이라도 이정도의 성능은 보장한다는 의미이기 때문
• Ω (오메가) 표기법: Ω(N)
  • 최상의 실행 시간을 표기
• Θ (세타) 표기법: Θ(N)
  • 알고리즘 평균 실행 시간을 표기

대문자 O 표기법

• 빅 오 표기법, Big-O 표기법 이라고도 부름
• O(입력) : 입력 n 에 따라 결정되는 시간 복잡도 함수
• 표현식에 가장 큰 영향을 미치는 n 의 단위로 표기
  👉 상수횟수는 무조건 O(1)
  👉 n번, n + 10 번, 또는 3n + 10 번등 실행한다 : O(n), 𝑛2 번, 𝑛2 + 1000 번, 100𝑛2 - 100, 또는 300𝑛2 + 1번등 실행한다 : O(𝑛2)

---

📝 마치며

복잡도 계산의 핵심을 정리했다. 이정도는 알고있으면 좋을것 같다. 시간복잡도의 반복문이 핵심!