최상의 경우 스왑 및 비교를위한 이진 삽입 정렬 복잡성
바이너리 삽입 정렬의 복잡성은 무엇일까요? 그리고 얼마나 많은 스왑과 비교가 이루어 집니까?
O(n(LG n))
비교 일 수도 있지만 확실하지 않습니다. 최악의 경우 실제로 N^2
스왑입니다. 최고는 어떻습니까?
답변
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))
.
여기 에 사용 된 코드 는이 저장소에서 사용할 수 있습니다 .