시간 복잡도

실제 코딩 테스트 문제의 시간 제한은 1~5초 가량이며,
보통 연산 횟수가 10억을 넘어가도록 작성하면 오답 판정 받을 수 있음에 주의해야 한다.

시간 제한이 1초인 문제의 경우

• N의 범위가 500: 시간 복잡도가 O(N³) 알고리즘을 설계하면 문제를 풀 수 있다.

• N의 범위가 2,000: 시간 복잡도가 O(N²) 알고리즘을 설계하면 문제를 풀 수 있다.

• N의 범위가 100,000: 시간 복잡도가 O(NlogN) 알고리즘을 설계하면 문제를 풀 수 있다.

• N의 범위가 10,000,000: 시간 복잡도가 O(N) 알고리즘을 설계하면 문제를 풀 수 있다.

공간 복잡도

공간 복잡도를 표기할 때도 빅오 표기법을 이용한다. 일반적으로 메모리 사용량 기준은 MB 단위로 제시된다.

정수형 자료형인 int를 기준으로 배열 크기에 따른 메모리 사용량은 다음과 같다.

• int a[1000]: 4KB

• int a[1000000]: 4MB

• int a[2000][2000]: 16MB

Java int, long 범위