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

계산 항목으로 2가지로 나뉨

1. 시간 복잡도→ 알고리즘 실행속도
2. 공간 복잡도 → 알고리즘이 사용하는 메모리 사이즈

<aside> 🤨 프로그래밍에서 시간 복잡도에 가장 영향을 많이 미치는 요소는 반복문이고, 입력의 크기가 커지면 커질수록 반복문이 알고리즘 수행 시간을 지배합니다.

</aside>

알고리즘 성능 표기법

빅오 표기법(Big-O Notation)

알고리즘의 성능과 효율성을 표현하는데 사용되는 개념

주어진 알고리즘이 입력크기에 따라 얼마나 빠르게 실행되는지 나타냄

상수항과 작은 항목들은 무시하고 가장 큰 차수의항만을 고려

ex) 3N³ + 2N²+ 1,000,000,000 →차수가 가장 큰 항만 남기므로 O(N³)

1. **O(1)**→ 상수 시간 알고리즘. 입력 크기에 상관없이 항상 일정한 실행 시간을 갖음

2. O(log n)→ 로그 시간 알고리즘. 입력 크기가 증가함에 따라 실행 시간이 로그

3. **O(n)**→ 선형 시간 알고리즘. 입력 크기에 비례하여 실행 시간이 증가함