Big O(빅-오) 표기법
- n이란 입력값의 크기를 의미하는 것이고n에 의해 알고리즘이 받는 영향력(반복수)을 표기하는 것
- 보통 N 앞에 상수가 붙으면 해당 상수는 로직에 큰 변화를 볼 수 없으므로 생략한다.
ex) 3N -> N, 2N^2 -> N^2 - 알고리즘의 최악의 수를 값으로 표현
💡 시간 복잡도 그래프
- 입력 값의 변화에 따라 코드를 실행할 때 걸리는 시간이 어떻게 달라지는지에 따라 시간 복잡도를 표현한다.
위 그림에서 볼 수 있듯이 연산 방법에 따라 구현되는 시간 복잡도가 매우 크게 달라진다. 입력 값과 주어진 제한 시간을 고려하여 코드의 시간복잡도를 잘 선택해야 한다.
1. O(1)
- 입력되는 데이터 크기에 상관없이 항상 일정한 시간이 걸리는 알고리즘
2. O(N)
- 입력 데이터의 크기에 비례해서 처리 시간이 걸리는 알고리즘
N이 늘어날 때마다 처리시간이 1증가하여 처리 시간이 선형적으로 증가
3. O(log N)
- 입력 데이터가 처리시간이 증가할수록 시간이 절반으로 줄어드는 형태의 알고리즘
4. O(N^2)
- 입력 데이터 크기의 제곱만큼 비례하여 처리 시간이 증가하는 알고리즘
처리 속도가 시간이 지날수록 기하급수적으로 커짐
5. O(2^N)
- N이 하나씩 증가할 때마다 걸리는 시간이 배로 증가하며 가장 느린 시간 복잡도를 갖는다.
