1. 시간/공간 복잡도 알아야 하는 이유
주어진 조건에 따라 접근법 유추 가능
2. 빅오표기법
: 알고리즘의 효율성 표기해주는 표기법
3. 특징
- 상수항 무시 | O(N+5) → O(N)
- 계수 무시 | O(3N) → O(N)
- 최고차항만 표기 | O(3N^3 + 2N^2 + N + 5 ) → O(N^3)
시간복잡도 : 입력된 N의 크기에 따라 실행되는 조작의 수
공간복잡도 : 알고리즘이 실행될 때 사용하는 메모리의 양
4. 빠른 순서
👍O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)👎
빅오 표기법 | 명칭 | 설명 |
O(1) | 상수시간 (Constant time) | 문제를 해결하는데 오직 한 단계 처리 |
O(log n) | 로그시간 (Log time) | 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듦 |
O(N) | 선형시간 | 문제를 해결하기 위한 입력 N만큼의 단계가 필요 |
O(N log N) | 로그선형시간 | 문제를 해결하기 위한 단계의 수가 N번에 그 하나의 N번당 단계들이 연산마다 특정 요인에 의해 줄어듦 |
O(N^2) | 이차시간 | 문제를 해결하기 위한 단계의 수는 입력값 N의 제곱 |
O(2^N) | 지수시간 | 문제를 해결하기 위한 단계의 수는 주어진 상수값 2의 N제곱 |
5. 문제조건에서 힌트 얻는 공식
1억번 연산 = 1초
시간제한이 1초이고, N의 범위는 2000인 경우,
O(N) : 2000번 연산 - 통과
O(N^2) : 4,000,000번 연산 -통과
O(N^3) : 8,000,000,000 번 연산 - 실패
- N의 범위 400인 경우, O(N^3) 알고리즘 설계시 통과
- N의 범위 2000인 경우, O(N^2) 알고리즘 설계시 통과
- N의 범위 100,000인 경우, O(N log N) 알고리즘 설계시 통과
- N의 범위 10,000,000인 경우, O(N)알고리즘 설계시 통과
6. 공간복잡도
int : 4byte
int a[1000] : 4KB
int a[1000000] : 4MB
int a[2000][2000] : 16MB
보통 메모리 사용량을 128~512MB로 제한
일반적인 경우에서는 배열의 크기가 1,000만 단위를 넘지 않도록 설계해야 함.
'🏷️CS > Algorithm' 카테고리의 다른 글
[코테 스터디] 4주차 : 동적계획법 (0) | 2024.07.01 |
---|---|
[코테 스터디] 3주차 : 그리디 (0) | 2024.06.24 |
[코테 스터디] 2주차 : DFS/BFS (1) | 2024.06.17 |
[코테 스터디] 1주차 : 자료구조 / 이진탐색 (1) | 2024.06.10 |
[백준] 1966 (프린터 큐) (2) | 2023.07.26 |