algorithm - iniciar - ¿En qué medida es O(n+k) la complejidad de la clasificación de grupos si implementamos grupos utilizando listas vinculadas?
mailchimp gratis (1)
Tengo curiosidad acerca de por qué la ordenación de cubetas tiene un tiempo de ejecución de O (n + k) si usamos cubetas implementadas con listas vinculadas. Por ejemplo, supongamos que tenemos esta entrada:
n = no of element= 8
k = range = 3
array = 2,2,1,1,1,3,1,3
Los cubos se verán así:
1: 1 -> 1 -> 1 -> 1
2: 2 -> 2
3: 3 -> 3
El tiempo total empleado en la inserción en estos grupos es O (n), suponiendo que almacenemos un puntero de cola en las listas vinculadas.
Para eliminar, tenemos que ir a cada grupo y luego eliminar cada nodo en ese grupo. Por lo tanto, la complejidad debe ser O (K * longitud promedio de la lista de enlaces del grupo) ya que estamos atravesando cada lista vinculada.
Sin embargo, leí que la complejidad de la clasificación de cubeta es O (n + k). ¿Por qué esto no concuerda con mi análisis? Por favor, corrígeme ya que todavía estoy aprendiendo complejidad computacional.
Su análisis es casi correcto, pero falta un detalle importante.
En este momento, es correcto que la iteración a través de la matriz de entrada para distribuir los elementos en cubos lleva tiempo O (n). Sin embargo, está un poco apagado cuando dice que la cantidad total de tiempo requerido para ensamblar la matriz es O (k * (número promedio de elementos por cubo)). Tenga en cuenta que debido a que hay n elementos y k cubetas, esto saldría a O (k * (n / k)) = O (n), para un tiempo de ejecución total de O (n). Para ver por qué la respuesta real es O (n + k), debemos analizar más detenidamente ese término big-O.
Para empezar, tiene toda la razón de que la cantidad promedio de tiempo que gasta en cada cubo es O (n / k). Luego dice que dado que hay k cubetas, el tiempo de ejecución total es O (k * (n / k)) = O (n). Sin embargo, esto es incorrecto: en particular, no es cierto que k * O (n / k) = O (n). La razón de esto es que el término O (n / k) está ocultando un factor constante. Cuando visita cada cubeta y observa los elementos que contiene, no lleva exactamente n / k tiempo, ni siquiera un múltiplo constante de n / k tiempo. Por ejemplo, ¿qué pasa si el cubo está vacío? En ese caso, todavía está gastando una cierta cantidad de tiempo mirando el cubo, ya que tiene que determinar que no debe iterar sobre sus elementos. Por lo tanto, una representación más precisa del tiempo requerido por grupo es algo como c 0 (n / k) + c 1 , donde c 0 y c 1 son constantes específicas de la implementación. Esta expresión es, por supuesto, O (n / k).
El problema es lo que sucede cuando multiplicas esta expresión por k para obtener la cantidad total de trabajo realizado. Si usted calcula
k * (c 0 (n / k) + c 1 )
Usted obtiene
c 0 n + c 1 k
Como puede ver, esta expresión depende directamente de k, por lo que el tiempo de ejecución total es O (n + k).
Una forma más directa de llegar a este resultado sería mirar el código para el segundo paso de la clasificación de la categoría, que se ve así:
For each bucket b:
For each element x in b:
Append x to the array.
¿Cuánto trabajo se hace en general? Bueno, hay k cubetas diferentes, por lo que el bucle más externo debe tomar al menos O (k) tiempo, porque tenemos que buscar en cada cubeta. En el interior, el bucle interno ejecutará un total de O (n) veces en general, porque hay un total de n elementos distribuidos en los cubos. De esto, obtenemos el tiempo de ejecución total O (n + k).
La razón por la que esto es importante es que significa que si intenta hacer una clasificación de cubetas con una gran cantidad de cubetas (por ejemplo, mucho mayor que n), el tiempo de ejecución puede estar dominado por el tiempo requerido para escanear todas las cubetas en busca de Los cubos que realmente usaste, incluso si la mayoría de ellos están vacíos. La razón por la que la clasificación de radix es útil es que utiliza múltiples iteraciones de clasificación de depósito donde solo hay dos depósitos, que se ejecutan en el tiempo O (n + 2) = O (n). Ya que solo necesita hacer iteraciones O (lg U) de esto (donde U es el valor máximo en la matriz), el tiempo de ejecución es O (n lg U) en lugar de la O (n + U) que obtendría del depósito tipo, que es mucho peor.
¡Espero que esto ayude!