arrays - programacion - ¿Es posible invertir una matriz con espacio extra constante?
matrices en matlab programacion (2)
Digamos que tengo una matriz A con n elementos únicos en el rango [0, n) . En otras palabras, tengo una permutación de los enteros [0, n).
¿Es posible transformar A en B usando O (1) espacio extra (también conocido como AKA en el lugar) de manera que B [A [i]] = i ?
Por ejemplo:
A B
[3, 1, 0, 2, 4] -> [2, 1, 3, 0, 4]
Invertir una matriz A requiere que encontremos una permutación B que cumpla con el requisito A[B[i]] == i para todo i .
Para construir el inverso en el lugar, tenemos que intercambiar elementos e índices configurando A[A[i]] = i para cada elemento A[i] . Obviamente, si simplemente iteráramos en A y realizáramos el reemplazo mencionado, podríamos anular los próximos elementos en A y nuestro cálculo fallaría.
Por lo tanto, tenemos que intercambiar elementos e índices a lo largo de los ciclos de A siguiendo c = A[c] hasta que alcancemos el índice de inicio de nuestro ciclo c = i .
Cada elemento de A pertenece a uno de esos ciclos. Dado que no tenemos espacio para almacenar si un elemento A[i] ya ha sido procesado y debe omitirse, debemos seguir su ciclo: Si alcanzamos un índice c < i , sabríamos que este elemento es parte de Un ciclo previamente procesado.
Este algoritmo tiene una complejidad en el peor tiempo de ejecución de O (n²) , una complejidad promedio en el tiempo de ejecución de O (n log n) y una complejidad en el mejor caso de ejecución de O (n) .
function invert(array) {
main:
for (var i = 0, length = array.length; i < length; ++i) {
// check if this cycle has already been traversed before:
for (var c = array[i]; c != i; c = array[c]) {
if (c <= i) continue main;
}
// Replacing each cycle element with its predecessors index:
var c_index = i,
c = array[i];
do {
var tmp = array[c];
array[c] = c_index; // replace
c_index = c; // move forward
c = tmp;
} while (i != c_index)
}
return array;
}
console.log(invert([3, 1, 0, 2, 4])); // [2, 1, 3, 0, 4]
Ejemplo para A = [1, 2, 3, 0] :
El primer elemento 1 en el índice 0 pertenece al ciclo de los elementos 1 - 2 - 3 - 0. Una vez que cambiamos los índices 0, 1, 2 y 3 a lo largo de este ciclo, hemos completado el primer paso.
El siguiente elemento 0 en el índice 1 pertenece al mismo ciclo y nuestro control nos lo dice en un solo paso (ya que es un paso hacia atrás).
Lo mismo se aplica a los elementos restantes 1 y 2 .
En total, realizamos 4 + 1 + 1 + 1 ''operaciones''. Este es el mejor de los casos.
Sí, es posible, con el algoritmo de tiempo O (n ^ 2):
Tome el elemento en el índice 0, luego escriba 0 en la celda indexada por ese elemento. Luego use solo el elemento sobrescrito para obtener el siguiente índice y escriba el índice anterior allí. Continúe hasta que vuelva al índice 0. Este es el algoritmo de ciclo líder.
Luego haga lo mismo a partir del índice 1, 2, ... Pero antes de realizar cualquier cambio, realice el algoritmo de líder de ciclo sin ninguna modificación a partir de este índice. Si este ciclo contiene algún índice debajo del índice de inicio, simplemente omítalo.
O este algoritmo de tiempo O (n ^ 3):
Tome el elemento en el índice 0, luego escriba 0 en la celda indexada por ese elemento. Luego use solo el elemento sobrescrito para obtener el siguiente índice y escriba el índice anterior allí. Continuar hasta volver al índice 0.
Luego haga lo mismo a partir del índice 1, 2, ... Pero antes de realizar cualquier cambio, realice el algoritmo de líder de ciclo sin ninguna modificación a partir de todos los índices anteriores. Si el índice actual está presente en cualquier ciclo anterior, simplemente omítalo.
He escrito (ligeramente optimizado) la implementation del algoritmo O (n ^ 2) en C ++ 11 para determinar cuántos accesos adicionales se necesitan para cada elemento en promedio si se invierte la permutación aleatoria. Aquí están los resultados:
size accesses
2^10 2.76172
2^12 4.77271
2^14 6.36212
2^16 7.10641
2^18 9.05811
2^20 10.3053
2^22 11.6851
2^24 12.6975
2^26 14.6125
2^28 16.0617
Mientras que el tamaño crece exponencialmente, el número de accesos a elementos crece de forma casi lineal, por lo que la complejidad del tiempo esperado para permutaciones aleatorias es algo como O (n log n).