본문 바로가기
코딩테스트/개념정리

시간/공간복잡도 개념(코테 대비 팁)

by 하루하루 나아가기 2024. 5. 13.
반응형

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

반응형

댓글