[JAVA] 시간복잡도와 공간복잡도 정리(코테용)

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

N의 범위가 500 : O(N^3) 알고리즘

N의 범위가 2000 : O(N^2) 알고리즘

N의 범위가 100,000 : O(NlogN) 알고리즘

- 병합정렬

N의 범위가 10,000,000 : O(N) 알고리즘

 

공간 복잡도

int arr[1000] : 4KB

int arr[1000000] : 4MB

 

자료구조에 따른 시간복잡도

ArrayList

- 접근 : O(1)

- 마지막 값 삽입/삭제 : O(1)

- i번째 값 삽입/삭제 : O(n)

-처음 값 삽입/삭제 : O(n)

 

LinkedList

- 접근 : O(n)

- 마지막 값 삽입/삭제 : O(n)

- i번째 값 삽입/삭제 : O(n)

- 처음값 삽입, 삭제 : O(n)

 

Arrays.sort 는 DualPivotQuickSort를 이용하여 O(N^2)

Collections.sort 는 TimeSort를 이용하여 O(NlogN)