1. 시간/공간 복잡도 알아야 하는 이유
•
시간 복잡도/공간복잡도가 문제의 힌트가 될 수 있다.
•
주어진 조건에 따라 접근법을 유추할 수 있다.
•
같은 문제도,
◦
브루트 포스 : 시간복잡도 -
◦
DP : 시간복잡도 -
◦
카데인 : 시간복잡도 -
2. 빅오 표기법
•
빅오표기법 : 알고리즘의 효율성을 표기해주는 표기법
•
빅오 표기법 특징
◦
상수항 무시
◦
계수 무시
◦
최고차항만 표기
•
시간복잡도 : 입력된 N의 크기에 따라 실행되는 조작의 수
•
공간복잡도 : 알고리즘이 실행될 때 사용하는 메모리의 양
시간복잡도 빠른 순서
문제 조건에서 힌트 얻는 공식
1억번 연산 = 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
공간 복잡도는 메모리 사용량을 128 ~ 512 MB로 제한
일반적인 경우에서는 배열의 크기가 1,000만 단위를 넘지 않도록 설계해야 한다.