Arrays.sort() 와 Collections.sort() 의 차이

albatross__3·2022년 3월 28일
0

백준 10989번 문제를 풀면서 알게된 사실 자바에서 배열의 정렬에 쓰이는 Arrays.sort()와 컬렉션(List,set..)의 정렬에 쓰이는 Collections.sort()가 시간,공간 복잡도 면에서 차이가 있음을 알게 되었다

시간복잡도

Arrays.sort(): 평균 O(NlogN) , 최악 O(N^2)
내부 알고리즘으로 DualPivotQuicksort 사용

Collections.sort(): 평균,최악 O(NlogN)
내부 알고리즘으로 Timsort(삽입+병합 정렬) 사용

공간복잡도

Arrays.sort()는 배열의 크기 만큼 고려하면 되지만 Collections.sort()는 객체를 추가하는 컬렉션이기 때문에 공간면에서 효율이 낮다

종합적으로 Collections.sort()가 시간 효율면에서는 좋아보이나 공간복잡도면에서 떨어지기 때문에 잘 고려해야 한다

profile
모든 즐겁게

0개의 댓글