Binary Insertion sortowanie złożoności dla swapów i porównań w najlepszym przypadku

Jan 18 2021

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^2zamiany. A co z najlepszymi?

Odpowiedzi

1 wsdookadr Jan 19 2021 at 13:29

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-thiteracji 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 i1i 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-ioperacje (może to być więcej niż n-ioperacje 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.