패스트 캠퍼스 챌린지 8일차 - 자료구조 알고리즘 복잡도 표현 방법

목차

1. 알고리즘 복잡도 계산이 필요한 이유
2. 알고리즘 복잡도 계산 항목
3. 알고리즘 시간 복잡도의 주요 요소
4. 알고리즘 성능 표기법

 

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

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

---

2. 알고리즘 복잡도 계산 항목

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

가장 중요한 시간 복잡도를 꼭 이해하고 계산할 수 있어야 함

---

3.알고리즘 시간 복잡도의 주요 요소

• 반복문이 지배합니다.

---

4.알고리즘 성능 표기법

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

시간 복잡도 계산은 반복문이 핵심 요소임을 인지하고, 계산 표기는 최상, 평균, 최악 중, 최악의 시간인 Big-O 표기법을 중심으로 익히면 됨

 

https://bit.ly/37BpXiC