InsertionSort의 복잡성을 O (nlogn)까지 줄일 수 있습니까?

Question

Java에서 BinarySearch & ArrayLists를 사용하면 O (nlogn)에서 O (n2)까지 InsertionSOrt의 복잡성을 줄일 수 있는지 궁금합니다.

Answer 1

삽입 정렬에에 O (N2) 복잡도 기여 2 가지있다 : 요소를 교체하기에 적합한 위치 검색

1) - 반복 당 O (N)이다. 이진 검색을 사용하여 O (log n)로 줄일 수 있습니다.

2) 올바른 위치가 발견되면 요소를 오른쪽보다 큰 (또는보다 작게) 이동합니다. 최악의 경우 목록 앞에 요소를 삽입하면 정렬 된 목록의 나머지 요소를 모두 오른쪽으로 이동해야합니다. 최악의 경우는 반복 당 O (n)입니다. 것 이진 검색 &의 ArrayList를 사용

따라서 총 복잡성 :

O(n * n + n * log n) 

Answer 2

일종의 삽입에 대한 복잡성 : 정렬 할 수있는 모든 나머지 요소를 통해

1. 으로 반복. (n 개의 원소에 대해 O (n))

2. a. 다음 요소 (위치 k에서 말)가 pos k-1에있는 요소보다 큰 경우 아무 것도하지 않습니다 (확인은 O (1)입니다). 즉, O (n * 1)은 이미 모든 요소가 정렬 된 최상의 경우입니다.

   b. pos k의 요소가 k-1의 요소보다 작 으면 왼쪽 요소만큼 커질 때까지 요소를 왼쪽으로 이동 시키거나 비교할 요소가 남아 있지 않습니다. . 따라서 O (n * n)