[코테 스터디] 2주차 : 시간복잡도

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만 단위를 넘지 않도록 설계해야 함.