Binary Insertion sortowanie złożoności dla swapów i porównań w najlepszym przypadku
Jaka może być złożoność binarnego sortowania przez wstawianie? A ile dokonano zamiany i porównań?
Mogą to być O(n(LG n))
porównania, ale nie jestem pewien. W najgorszym przypadku są to rzeczywiście N^2
zamiany. A co z najlepszymi?
Odpowiedzi
Możesz łatwo pisać binarne sortowanie przez wstawianie, wykorzystując wbudowane funkcje, takie jak bisect_lefti list.pop(..)i 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
O najgorszym przypadku, ponieważ w i-th
iteracji pętli wykonujemy binarne przeszukiwanie wewnątrz sub-macierzy A[0..i]
, z 0<=i<n
, że należy podjąć log(i)
działania, więc teraz wiemy, musimy wstawić element na miejscu i1
i wstawiamy go, ale wstawianie oznacza, że musimy przesunąć wszystkie elementy, które za nim podążają, o jedną pozycję w prawo, a to przynajmniej n-i
operacje (może to być więcej niż n-i
operacje w zależności od miejsca wstawienia). Jeśli podsumujemy tylko te dwa, otrzymamy\sum_{i=1}^n log(i) + (n-i) = log(n!) + (n*(n+1))/2 ~ n*log(n) + (n*(n+1))/2
(w powyższym Wzór Stirlinga z log(n!)
jest używany)
Teraz strona wiki mówi
Z reguły można założyć, że człon najwyższego rzędu w dowolnej funkcji dominuje w tempie jej wzrostu, a tym samym definiuje jej kolejność w czasie wykonywania
Myślę więc, że wniosek byłby taki, że w najgorszym przypadku binarne sortowanie przez wstawianie ma O(n^2)
złożoność.
Zobacz też:
- sortowanie przez wstawianie przy użyciu wyszukiwania binarnego
- sortowanie przez wstawianie z wyszukiwaniem binarnym
- analiza binarnego sortowania przez wstawianie
- binarne sortowanie i złożoność wstawiania
Następnie próbowałem sprawdzić, jak to działa na listach odwróconych ( n,n-1,n-2,..,1
) i naprzemiennych ( 0,n-1,1,n-2,2,n-3,...
). I dopasowałem je (używając modułu wzrostu dopasowania ) do różnych wskaźników wzrostu, ta część jest tylko przybliżeniem. Kolejność odwrotna została dopasowana do czasu wielomianowego, a kolejność przemienna została dopasowana do czasu quasiliniowego
Najlepszy przypadek jest wyjaśniony tutaj . Jeśli lista jest już posortowana, to nawet jeśli nie dokonamy żadnych zamian, wszystkie wyszukiwania binarne są nadal wykonywane, co prowadzi do O(n*log(n))
.
Kod użyty tutaj jest dostępny w tym repozytorium.