Complejidad de clasificación de inserción binaria para intercambios y comparación en el mejor de los casos

Question

¿Cuál podría ser la complejidad de la ordenación por inserción binaria? ¿Y cuántos intercambios y comparaciones se hacen?

Pueden ser O(n(LG n))comparaciones, pero no estoy seguro. En el peor de los casos, se trata de N^2intercambios. ¿Qué pasa con los mejores?

Answer 1

Puede escribir ordenación por inserción binaria fácilmente aprovechando las funciones integradas como bisect_lefty list.pop(..)y 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

En el peor de los casos, ya que en la i-thiteración del bucle, realizamos una búsqueda binaria dentro del subarreglo A[0..i], con 0<=i<n, que debería tomar log(i)operaciones, por lo que ahora sabemos que tenemos que insertar un elemento en la ubicación i1y lo insertamos, pero la inserción significa que tenemos que empujar todos los elementos que la siguen una posición a la derecha, y eso es al menos n-ioperaciones (puede ser más que n-ioperaciones dependiendo de la ubicación de inserción). Si sumamos solo estos dos, obtenemos\sum_{i=1}^n log(i) + (n-i) = log(n!) + (n*(n+1))/2 ~ n*log(n) + (n*(n+1))/2

(en la aproximación de Stirling anterior log(n!)se está utilizando)

Ahora la página wiki dice

Como regla general, se puede suponer que el término de orden más alto en cualquier función dada domina su tasa de crecimiento y, por lo tanto, define su orden de tiempo de ejecución.

Así que creo que la conclusión sería que, en el peor de los casos, el tipo de inserción binaria tiene O(n^2)complejidad.

Ver también:

• ordenación por inserción mediante búsqueda binaria
• ordenación por inserción con búsqueda binaria
• análisis de ordenación por inserción binaria
• ordenación y complejidad de inserción binaria

Luego traté de verificar cómo se está desempeñando en listas invertidas ( n,n-1,n-2,..,1) y alternas ( 0,n-1,1,n-2,2,n-3,...). Y los ajusté (usando el módulo de crecimiento de coincidencias ) a diferentes tasas de crecimiento, esta parte es solo una aproximación. El orden inverso se ajustó al tiempo polinomial y el orden alterno se ajustó al tiempo cuasilineal

El mejor de los casos se explica aquí . Si la lista ya está ordenada, incluso si no hacemos ningún intercambio, todas las búsquedas binarias todavía se están realizando, lo que conduce a O(n*log(n)).

El código utilizado aquí está disponible en este repositorio.