목차
1. 시간/공간 복잡도 알아야 하는 이유
2. 빅오표기법
3. 시간복잡도 구하는 연습
4. 문제조건에서 힌트 얻는 공식

1. 시간/공간 복잡도 알아야 하는 이유

주어진 조건에 따라 접근법을 유추할 수 있다

• 같은 문제 다른 접근

✅ 알고리즘 : 브루트포스
✅ 시간복잡도 : O(N^2)

---

✅ 알고리즘 : DP
✅ 시간복잡도 : O(N)
✅ 공간복잡도 : O(N)

---

✅ 알고리즘 : 카데인
✅ 시간복잡도 : O(N)
✅ 공간복잡도 : O(1)

2. 빅오표기법

빅오표기법

: 알고리즘의 효율성을 표기해주는 표기법

빅오표기법 특징

✔️ 상수항 무시 O(N+5) ➡️ O(N)
✔️ 계수 무시 O(3N) ➡️ O(N)
✔️ 최고차항만 표기 O(3N^3+2N^2+N+5)

- 시간복잡도 : 입력된 N의 크기에 따라 실행되는 조작의 수
- 공간복잡도 : 알고리즘이 실행될 때 사용하는 메모리의 양

시간복잡도 빠른 순서

O(1) < O(logN) < O(N) < O(N*logN) < O(N^2) < O(2^N) < O(N!)

3. 시간 복잡도 구하는 연습

ex 1) - 두 그룹의 반복문은 연속적이므로 최종 복잡도는 두 그룹의 복잡도를 더한다
- 시간 복잡도는 O(N^2) + O(n^2) = O(N^2)입니다

ex 2) - 중첩 반복문에서는 내부 반복문을 살펴봐야한다. 시간 복잡도는 내부 반복문에서 계산되는데, 처음에는 n 시간동안 실행하고 다음에는 n/2 시간의 형태로 실행합니다(n+n/2+n/4+n/8+n/16+...)

• 시간 복잡도는 O(n)입니다

4.문제조건에서 힌트 얻는 공식

1억번 연산 = 1초로 생각하기
시간제한이 1초 경우 예시

N의 범위는 2000인 경우
O(N) ➡️ 2000번 연산, 1억 이하여서 가능
O(N^2) ➡️ 4,000,000번 연산, 1억 이하여서 가능
O(N^3) ➡️ 8,000,000,000번 연산, 1억 이상이므로 불가능

• N의 범위 400인 경우
  O(N^3) 알고리즘을 설계하면 문제를 풀 수 있다
• N의 범위 2,000인 경우
  O(N^2) 알고리즘을 설계하면 문제를 풀 수 있다
• N의 범위 100,000인 경우
  O(NlogN) 알고리즘을 설계하면 문제를 풀 수 있다
• N의 범위 10,000,000인 경우
  O(N) 알고리즘을 설계하면 문제를 풀 수 있다

**주어진 조건에 따라 접근법 유추할 수 있다
시간복잡도를 고려한 설계가 가능하다**

공간복잡도

int : 4byte
int a[1000] : 4KB
int a[1000000] : 4MB
int a[2000][2000] : 16MB

공간복잡도 보통 메모리 사용량을 128 ~ 512MB로 제한

일반적인 경우에서는 배열의 크기가 1,000만 단위를 넘지 않도록 설계해야 한다