1. 시간/공간 복잡도를 알아야 하는 이유
2. 빅오(Big O)표기법 : 알고리즘의 성능을 분석할 때 사용하는 수학적 표현 방식이다. 이는 특히 알고리즘이 처리해야할 데이터의 양이 증가할 때, 그 알고리즘이 얼마나 빠르게 실행되는지 나타낸다. 여기서 중요한 것은 알고리즘의 정확한 실행 시간을 계산하는 것이 아니라, 데이터 양의 증가에 따른 성능의 변화 추세를 이해하는 것이다.
- 시간 복잡도 : 입력된 N의 크기에 따라 실행되는 조작의 수
1. O(1) - 상수 시간 : 입력 데이터의 크기에 관계없이 알고리즘의 실행 시간이 일정하다.
예) 배열에서 인덱스를 사용하는 경우
2. O(n) - 선형 시간 : 알고리즘의 실행 시간이 입력 데이터의 크기에 비례하여 증가한다.
예) 배열의 검색, 배열의 모든 요소를 순회하는 경우
3. O(n^2) - 제곱 시간 : 알고리즘의 실행 시간이 입력 데이터의 크기의 제곱에 비례하여 증가한다.
예) 보통 이중 루프를 사용하는 알고리즘에서 나타남
4. O(log n) - 로그 시간 : 알고리즘의 실행 시간이 데이터 크기의 로그에 비례하여 증가한다.
예) 이진 탐색
5. O(n log n) - 선형 로그 시간
예) 많은 효율적인 정렬 알고리즘들
- 공간 복잡도 : 알고리즘이 실행될 때 사용하는 메모리의 양
*코테준비할 때 공식
시간복잡도
1억번 연산 = 1초로 생각하기
N의 범위는 2000인 경우,
O(N) -> 2000번 연산, 1억 이하여서 가능
O(N^2) -> 4,000,000번 연산, 1억 이하여서 가능
O(N^3) -> 8,000,000,000번 연산, 1억 이상이므로 불가능
공간복잡도
int : 4byte
int a[1000] : 4KB
int a[1000000] : 4MB
int a[2000][2000] : 16MB
공간복잡도는 보통 메모리 사용량을 128~512MB로 제한
일반적인 경우에는 배열의 크기가 1,000만 단위를 넘지 않도록 설계해야 한다.
'코딩테스트 > 개념정리' 카테고리의 다른 글
동적 계획법(DP:Dynamic programming) 개념 및 구현 (0) | 2024.05.27 |
---|---|
DFS와 BFS 개념 및 구현 (0) | 2024.05.13 |
[자료구조] 스택(stack) ,큐(Queue) / [알고리즘] 이진 탐색(binary search) (1) | 2024.05.06 |
댓글