primitive type (ex. int) Arrays를 Arrays.sort를 호출해서 소트하면 최악의 경우 O(n^2)입니다.

Arrays.sort에 primitive type이 들어가면 merge sort가 아닌 dual-pivot quicksort가 이루어집니다.

이는 웬만한 데이터로는 잘 저격되지 않지만,  https://www.acmicpc.net/board/view/34491 와 같이 특성을 파악하면 O(N^2)으로 만드는 저격이 가능합니다.  https://blog.kyouko.moe/29?category=767011 를 읽어보세요.

오늘도 새로운 사실을 배워갑니다.

감사합니다!

ArrayList는 jaejin님이 아시고 계신 것처럼

'내부적으로 배열 확장을 하기 때문에 추가적인 연산이 필요한 것' 이 맞습니다.

그러면 배열 확장을 하기 위해서, 추가적인 복잡도를 어떻게 계산하면 좋을까요?

보통 Java의 vector는 grow rate가 2, arrayList는 1.5입니다. (StringBuilder는 2일 건데 최근에 어떻게 변했는지는 F5 눌러서 뜯어보세요.)

일단 확장한 직후의 Space를 N이라고 해 봅시다.

그러면 1.5N이 될 때 까지 확장은 안 할 겁니다. 그 이후에 확장을 하겠죠.

이렇게 가정을 해 봅시다.

배열의 뒤에다가 원소를 넣는 연산 = 원소 하나를 다른 배열에 복사하는 연산 = 공간 1만큼 할당하는 연산 

= delete 하는 연산 = 1로 잡아봅시다. (물론 이보다 더 클 수도 있을 겁니다. 특히 할당 비용은)

일단. N에서 1.5N이 될 때 까지 그냥 add만 하는 경우, 1.5N만큼 소모됩니다.

다음에, 1.5N만큼 되었을 때, 크기가. 이 때 확장이 일어나야 할 건데.

(1) 2.25N만큼의 배열을 새로 할당한다.

(2) 1.5N만큼을 새 배열에 복사한다.

(3) 1.5N만큼의 배열을 delete 한다. (gc가 알아서 잘 처리해 줄 겁니다만 그 비용까지 고려해 봅시다.)

그러면 (2.25 + 3)/0.5 = 대략 10.5 정도의 비용이 드네요. ㅋㅋ

상수가 크지만 어찌 되었던 O(1)은 보장이 됩니다. 이걸 N번 연산한다. 평균적으로 보면 10N이죠. 이런 분석 방법을 분할 상환 방법 이라고 이야기를 합니다.

그리고 merge sort를 하면 NlogN입니다. 어찌 되었던 복잡도는 O(NlogN)인데

이는 dual pivot을 쓰는 퀵 소트의 최악 복잡도인 O(N^2)보다는 낮습니다. 따라서 빠를 수 밖에 없어요.

- grow rate : 동적 배열이 확장이 된 후/확장이 되기 전의 비율을 나타낸 것.

친절한 설명 감사합니다!

ArrayList의 확장이 growrate를 따라 확장된다는 사실을 처음 알게 되었습니다. 그간 디버깅할때 ArrayList 초기 크기가 10이어서 항상 10씩 늘어나는 줄 막연히 생각해왔는데ㅎㅎ;;

그런데 설명하신대로 라면 ArrayList에 N개의 요소를 add할 때의 시간복잡도는 O(NlogN)이 아닌가 싶습니다.

log_1.5N=a라 할 때 ArrayList는 총 a번의 확장을 하게 되고 i번째 확장할 때의 연산 횟수는 10.5*(1.5^i)이므로 전체 시간복잡도는  O(NlogN)이 될 것 같습니다.

ArrayList의 확장이 O(NlogN)이어도 mergeSort 역시 O(NlogN)이니 결국은 O(NlogN)라는 점은 달라지지 않겠네요.

덕분에 많은 사실을 알게 되었습니다!

확장은 amortized O(N)입니다. 로그가 붙지 않습니다. 단순하게 O(N)의 연산을 O(logN)번 한다고 생각해서는 안 되고, 실제로 시그마를 했을 때 얼마가 나오는지 확인해 보세요.

https://zeddios.tistory.com/60

저 댓글을 쓸 때에도 등비수열의 합으로 계산을 했는데 logN이 왜 튀어나왔는지 저도 모르겠네요;; 정신이 없었나 봅니다ㅋㅋ