algorithm - keywords - ¿Por qué la combinación iterativa de k-way O(nk ^ 2)?

meta tags seo 2018

Question

k-way merge es el algoritmo que toma como entrada k ordenaciones ordenadas, cada una de tamaño n. Emite una única matriz ordenada de todos los elementos.

Lo hace mediante el uso de la rutina "fusionar" central al algoritmo de ordenación por fusión para combinar la matriz 1 con la matriz 2, y luego la matriz 3 con esta matriz combinada, y así sucesivamente hasta que todas las k matrices se hayan fusionado.

Había pensado que este algoritmo es O (kn) porque el algoritmo atraviesa cada una de las k matrices (cada una de longitud n) una vez. ¿Por qué es O (nk ^ 2)?

Answer 1

k-way merge es el algoritmo que toma como entrada k ordenaciones ordenadas, cada una de tamaño n. Emite una única matriz ordenada de todos los elementos.

Pensé que este algoritmo es O (kn)

Podemos refutar eso por contradicción. Defina un algoritmo de clasificación para m elementos que utiliza su algoritmo con k = m y n = 1. Según la hipótesis, el algoritmo de clasificación tiene éxito en O (m) tiempo. Contradicción, se sabe que cualquier algoritmo de clasificación tiene el peor caso al menos O (m log m).

Answer 2

1. Tienes k arreglos cada uno con n elementos. Esto significa elementos k * n totales.

2. Considérelo una matriz de k * n. Para agregar el primer elemento a la matriz combinada / final, debe comparar los jefes de k matrices. Esto significa que para un elemento en el conjunto final debe hacer k comparaciones.

Entonces, de 1 y 2, para elementos K n, el tiempo total tomado es O (k k * n).

Answer 3

1) Tienes k arreglos ordenados, cada uno de tamaño n. Por lo tanto, el número total de elementos = k * n

2) Tome el primer elemento de todos los k arrays y cree una secuencia. Luego encuentra el mínimo de esta secuencia. Este valor mínimo se almacena en la matriz de salida. El número de comparaciones para encontrar el mínimo de k elementos es k - 1.

3) Por lo tanto, el número total de comparaciones
= (comparaciones / elemento) * cantidad de elementos
= (k - 1) * k * n
= k ^ 2 * n // aproximadamente

Answer 4

En realidad, en el peor de los casos, habrá n comparaciones para el primer conjunto, 2n para el segundo, 3n para el tercero y pronto hasta (k - 1) n .
Entonces ahora la complejidad se vuelve simple

n + 2n + 3n + 4n + ... + (k - 1)n
= n(1 + 2 + 3 + 4 + ... + (k - 1))
= n((k - 1)*k) / 2
= n(k^2 - k) / 2
= O(nk ^ 2)

:-)

Answer 5

No estoy de acuerdo con otras respuestas. No tiene que comparar elementos 1 por 1 cada vez. Simplemente debe mantener los elementos K más recientes en un conjunto ordenado. Quita el más pequeño y lo relaciona con su siguiente elemento. Esto debería ser n.log (k)

article relevante. Descargo de responsabilidad: participé en escribirlo

Answer 6

Porque no atraviesa cada una de las k matrices una vez. La primera matriz se cruza k-1 veces, la primera como merge (array-1, array-2), la segunda como merge (merge (array-1, array-2), array-3) ... y así sucesivamente .

El resultado es k-1 se fusiona con un tamaño promedio de n * (k + 1) / 2 dando una complejidad de O (n * (k ^ 2-1) / 2) que es O (nk ^ 2).

El error que cometió fue olvidar que las fusiones se realizan en serie en lugar de en paralelo, por lo que las matrices no son todas de tamaño n.

Answer 7

Qué tal esto:

Paso 1: Fusionar matrices (1 y 2), matrices (3 y 4), y así sucesivamente. (combinaciones de matriz k / 2 de 2n, kn de trabajo total).

Paso 2: Fusionar arreglo (1,2 y 3,4), arreglos (5,6 y 7,8), y así sucesivamente (k / 4 se fusiona de 4n, trabajo total kn).

Paso 3: repite ...

Habrá log (k) tales "Pasos", cada uno con kn work. De ahí el trabajo total realizado = O (knlog (k)).

Incluso de lo contrario, si tuviéramos que ordenar todos los elementos de la matriz, podríamos fusionar todo en O (knlog (kn)) time.

Answer 8

Una implementación común mantiene una matriz de índices para cada una de las k matrices ordenadas {i_1, i_2, i__k}. En cada iteración, el algoritmo encuentra el siguiente elemento mínimo de todos los k arrays y lo almacena en la matriz de salida. Como está realizando iteraciones kn y escaneando k matrices por iteración, la complejidad total es O (k ^ 2 * n).

Aquí hay un pseudo-código:

Input: A[j] j = 1..k : k sorted arrays each of length n
Output: B : Sorted array of length kn

// Initialize array of indexes
I[j] = 0 for j = 1..k

q = 0

while (q < kn):
    p = argmin({A[j][I[j]]}) j = 1..k           // Get the array for which the next unprocessed element is minimal (ignores arrays for which I[j] > n)
    B[q] = A[p][I[p]]
    I[p] = I[p] + 1
    q = q + 1