최상의 경우 스왑 및 비교를위한 이진 삽입 정렬 복잡성

Jan 18 2021

바이너리 삽입 정렬의 복잡성은 무엇일까요? 그리고 얼마나 많은 스왑과 비교가 이루어 집니까?

O(n(LG n))비교 일 수도 있지만 확실하지 않습니다. 최악의 경우 실제로 N^2스왑입니다. 최고는 어떻습니까?

답변

1 wsdookadr Jan 19 2021 at 13:29

bisect_left및 list.pop(..)및 list.insert(..)다음 과 같은 내장 함수를 활용하여 이진 삽입 정렬을 쉽게 작성할 수 있습니다 .

def bininssort(L):
    n = len(L)
    i,j=0,0
    for i in range(1,n):
        j=i-1
        x=L.pop(i)
        i1=bisect_left(L,x,0,j+1)
        L.insert(i1,x)
    return L

최악의 경우에 대해, 상기 있기 때문에 i-th루프의 반복, 우리는 하위 배열 내부 이진 검색을 수행 A[0..i]하여, 0<=i<n해야하는, log(i)우리가 지금 우리가 위치에 요소를 삽입해야 알 수 있도록, 작업을 i1우리가 그것을 삽입하지만, 삽입은 그 뒤를 따르는 모든 요소를 ​​오른쪽으로 한 위치로 밀어야한다는 것을 의미하며, 이는 적어도 n-i작업입니다 ( n-i삽입 위치에 따라 작업 이상일 수 있음 ). 이 두 가지를 요약하면\sum_{i=1}^n log(i) + (n-i) = log(n!) + (n*(n+1))/2 ~ n*log(n) + (n*(n+1))/2

(위의 스털링 근사 의 log(n!)사용중인)

이제 위키 페이지는 말한다

어림짐작으로, 주어진 함수의 최상위 항이 성장률을 지배하고 따라서 런타임 순서를 정의한다고 가정 할 수 있습니다.

따라서 결론은 최악의 경우 이진 삽입 정렬이 O(n^2)복잡 하다는 것 입니다.

또한보십시오:

  • 이진 검색을 사용한 삽입 정렬
  • 이진 검색으로 삽입 정렬
  • 이진 삽입 정렬 분석
  • 이진 삽입 정렬 및 복잡성

그런 다음 reversed ( n,n-1,n-2,..,1) 및 교대 ( 0,n-1,1,n-2,2,n-3,...) 목록 에서 어떻게 수행되는지 확인하려고했습니다 . 그리고 저는 그것들을 ( matchgrowth 모듈을 사용하여 ) 다른 성장률에 맞추 었습니다 .이 부분은 단지 근사치입니다. 역순은 다항식 시간에 적합하고 교번 순서는 준 선형 시간에 적합했습니다.

가장 좋은 사례는 여기 에 설명되어 있습니다 . 목록이 이미 정렬 된 경우 스왑을 수행하지 않더라도 모든 이진 검색이 계속 수행되어 O(n*log(n)).

여기 에 사용 된 코드 는이 저장소에서 사용할 수 있습니다 .