Insertor Sort의 최악의 경우의 시간 복잡도가 올바르지 않습니다.

Question

안녕하세요 저는 알고리즘에 익숙하지 않아 매우 흥미 롭습니다.

삽입 정렬의 최악의 경우 시간 복잡성을 파악하려고하는데 O (n ** 2)로 언급됩니다. 대신 시간 복잡도를 O (N * logN)로 가질 수 있습니다. 여기

내 설명은,

삽입 정렬은 첫번째 요소를 살펴보고이 정렬됩니다 가정합니다. 다음으로 두 번째 요소를보고 이전 요소 인 sorted sublist와 비교하여 이전 요소 인 정렬 된 하위 목록의 요소와 비교하여 요소를 삽입합니다. 이 과정은 비슷하게 반복됩니다.

전처리 된 정렬 된 하위 목록에 요소를 삽입하는 것은 기본적으로 선형 검색이므로 O (N) 시간이 걸리고 n 요소에 대해 이러한 연산을 수행 할 때 O (N ** 2) .

그러나 이진 삽입을 사용하여 요소를 선행 작업 하위 목록에 삽입하는 경우 O (logn) 시간이 소요됩니다. 여기서 n은 부속 목록의 길이입니다. 기본적으로 이전 요소 인 정렬 된 하위 목록의 중간 요소와 새 요소를 비교하고 중간 요소보다 큰 경우 하위 요소의 중간 요소와 마지막 요소 사이에 새로운 요소가 놓입니다.

n 개의 항목에 대해 작업을 반복 할 때 O (N * logN)가 필요합니다. 선행 서브리스트가 정렬되어 있다는 것을 알고 있으므로 바이너리 검색 방식을 사용할 수 있습니다.

그래서 최악의 시간 복잡도는 O (N ** 2) 대신 O (N * logN)가되어서는 안됩니다.

Answer 1

예, O (log n)에 삽입 지점을 찾을 수 있지만 항목을 삽입 할 공간을 확보해야합니다. 그건 O (n) 시간이 걸립니다.

이 부분적으로 정렬 된 배열을 고려 :

[1,2,3,5,6,7,9,4] 

당신은 마지막 항목, 4에 도착을하고, 당신은 삽입 할 필요가있는 위치를 찾을 수 이진 검색을한다. 하지만 이제는 공간을 만들어야합니다. 즉, 항목 9, 7, 6 및 5를 배열의 한 위치 아래로 이동해야합니다. 이것이 삽입 정렬 O (n^2)를 만드는 이유입니다.