Análisis del algoritmo

Question

Considere una implementación recursiva de Mergesort que llama a Insertion Sort en sublistas más pequeñas que algún umbral. Si hay n llamadas a Mergesort, ¿cuántas llamadas habrá a Insertion Sort? ¿Por qué?

¿No dependería esto del umbral, o hay otra forma de verlo?

Answer 1

¿Cómo se consigue $n$ ¿fusionar tipos?

1. Se llama una vez para toda la lista. Se obtienen dos listas.
2. Se llama dos veces (una para cada una de las listas del paso anterior). Se obtienen cuatro listas.
3. Lo llamas cuatro veces...

Por lo tanto, el total es

$$1 + 2 + 4 + 8 + \cdots = \sum_{k=0}^m 2^k = 2^{m+1} - 1.$$

Ahora, ¿cuántos final llamadas (las que llaman a algún otro tipo, en su caso la inserción) tiene? Es el último sumando de arriba: $2^m$ . Entonces, se llama a la ordenación por inserción $2^m$ veces, dado que su ordenación de la fusión se llamó $n = 2^{m+1} - 1$ veces. O, en términos de $n$ , usted tiene $(n+1)/2$ llamadas a la ordenación de la inserción.

Para $n$ que no es de la forma $2^{m+1} - 1$ es decir, $2^{m+1} - 1 < n < 2^{m+2} - 1$ para algunos $m$ , tendrás un desequilibrio en las llamadas en el último nivel (suponiendo que estés haciendo todo lo más equilibrado posible). Entonces, tienes $2^m$ listas del $(m-1)$ -Primer paso y has llamado a merge sort $2^{m+1}-1$ tiempos. Todavía tienes

$$n' = n - 2^{m+1} + 1, \quad m = \lfloor \log_2 (n+1) \rfloor - 1,$$

llamadas a la ordenación por fusión, cada una de las cuales produce $2$ listas de $1$ . Por lo tanto, se obtiene

$$2n' + (2^m - n') = n - 2^m + 1$$

listas y, por tanto, otras tantas llamadas a la ordenación por inserción. Se trata de una generalización de la $n = 2^{m+1} - 1$ caso.

El umbral, dado que es un número constante de llamadas, afectará a la longitud de estas minilistas, no al número de llamadas. Si el umbral se da en función de la longitud de la lista que se está ordenando con la ordenación por inserción, entonces lo anterior no se aplica (pero sí se consigue que el número de llamadas a la ordenación por inserción dependa de la longitud de la lista).