rápido algoritmo de búsqueda de sumas en la matriz

Question

Estoy buscando un algoritmo rápido:

Tengo un int matriz de tamaño n, el objetivo es encontrar todos los patrones de la matriz que
x1, x2, x3 are different elements in the array, such that x1+x2 = x3

Para ejemplo, sé que hay una matriz int de tamaño 3 es [1, 2, 3], entonces solo hay una posibilidad: 1 + 2 = 3 (considere 1 + 2 = 2 + 1)

Estoy pensando en implementar Pares y Hashmaps para hacer que el algoritmo sea rápido . (El más rápido que tengo ahora es todavía O(n^2))

favor comparta su idea para este problema, gracias

Answer 1

Editar: La respuesta siguiente se aplica a una versión de este problema en la que solo desea un triplete que se suma a eso. Cuando los quiere todos, dado que potencialmente hay al menos O (n^2) salidas posibles (como lo señala ex0du5), e incluso O (n^3) en casos patológicos de elementos repetidos, no va a vencer el algoritmo simple O (n^2) basado en hashing (mapeo de un valor a la lista de índices con ese valor).

---

Esto es básicamente the 3SUM problem. Sin elementos potencialmente ilimitados, los algoritmos más conocidos son aproximadamente O(n^2), pero solo hemos demostrado que no puede ser más rápido que O(n lg n) para la mayoría de los modelos de computación.

Si los elementos enteros se encuentran en el rango [u, v], puede hacer una versión ligeramente diferente de esto en O(n + (v-u) lg (v-u)) con FFT. Voy a describir un proceso para transformar este problema en uno, resolverlo allí y luego encontrar la respuesta a su problema en base a esta transformación.

El problema que yo sepa cómo resolver con la FFT es encontrar una secuencia aritmética longitud-3 en una matriz: es decir, una secuencia a, b, c con c - b = b - a, o equivalentemente, a + c = 2b.

Desafortunadamente, el último paso de la transformación no es tan rápido como me gustaría, pero hablaré de eso cuando lleguemos allí.

---

Vamos a llamar a su matriz original X, que contiene números enteros x_1, ..., x_n. Queremos encontrar los índices i, j, k tales que x_i + x_j = x_k.

1. encontrar el mínimo y el máximo uv de X en O(n) tiempo.Deje que u' sea min(u, u*2) y v' sea max(v, v*2).

2. Construya una matriz binaria (cadena de bits) Z de longitud v' - u' + 1; Z[i] será verdadero si X o su doble [x_1*2, ..., x_n*2] contiene u' + i. Esto es O(n) para inicializar; simplemente recorra cada elemento de X y configure los dos elementos correspondientes de Z.

   Como estamos construyendo esta matriz, podemos guardar los índices de cualquier duplicado que encontremos en una lista auxiliar Y. Una vez que se completa Z, simplemente verificamos 2 * x_i para cada x_i en Y. Si alguno está presente, hemos terminado; de lo contrario, los duplicados son irrelevantes y podemos olvidarnos de Y. (La única situación un poco más complicada es si 0 se repite; entonces tenemos tres copias distintas de la misma para obtener una solución.)

   Ahora, una solución a su problema, es decir x_i + x_j = x_k, aparecerá en Z como tres evenly- espaciados, ya que algunas manipulaciones algebraicas simples nos dan 2*x_j - x_k = x_k - 2*x_i. Tenga en cuenta que los elementos en los extremos son nuestras entradas dobles especiales (desde 2X) y la que está en el medio es una entrada regular (de X).

3. Considérese Z como una representación de un polinomio p, donde el coeficiente por el término de grado i es Z[i]. Si X es [1, 2, 3, 5], entonces Z es 1111110001 (porque tenemos 1, 2, 3, 4, 5, 6 y 10); p es entonces 1 + x + x + x + x + x + x.

   Ahora, recuerdo de álgebra de la escuela que el coeficiente de x ^c en el producto de dos polinomios es la suma sobre todos a, b con a + b = c de coeficiente del primer polinomio para x ^a veces el coeficiente del segundo para x ^b. Por lo tanto, si tenemos en cuenta q = p, el coeficiente de x ^2j (para un j con Z[j] = 1) será la suma de todos los i de Z[i] * Z[2*j - i]. Pero dado que Z es binario, ese es exactamente el número de trillizos i, j, k que están espaciados en Z. Tenga en cuenta que (j, j, j) siempre es un triplete, por lo que solo nos preocupan aquellos con valores> 1.

   Entonces podemos usar un Fast Fourier Transform encontrar ^{p 2} en O(|Z| log |Z|) tiempo, donde |Z| es v' - u' + 1. Obtenemos otra serie de coeficientes; llámalo W.

4. Bucle sobre cada x_k en X. (Recuerde que nuestros espacios deseados uniformemente están centrados en un elemento de X, no 2*X). Si el W correspondiente para el doble de este elemento, es decir, W[2*(x_k - u')], es 1, sabemos que no es el centro de ninguna progresión no trivial y podemos Saltarlo. (Como se argumentó anteriormente, solo debería ser un número entero positivo)

   De lo contrario, podría ser el centro de una progresión que queremos (así que tenemos que encontrar i y j). Pero, desafortunadamente, también podría ser el centro de una progresión que no tiene nuestra forma deseada. Entonces tenemos que verificar. Pasa sobre los otros elementos x_i de X, y comprueba si hay un triple con 2*x_i, x_k, 2*x_j para algunos j (marcando Z[2*(x_k - x_j) - u']). Si es así, tenemos una respuesta; si pasamos por todo X sin un golpe, entonces la FFT encontró solo respuestas espurias, y tenemos que verificar otro elemento de W.

   Este último paso es por lo tanto O (n * 1 + (número de x_k con W [2 * (x_k - u ')]> 1 que en realidad no son soluciones)), que posiblemente sea O(n^2), que es Obviamente no está bien. Debería haber una manera de evitar generar estas respuestas espurias en la salida W; si supiéramos que cualquier coeficiente W apropiado definitivamente tiene una respuesta, este último paso sería O(n) y todo estaría bien.

   Creo que es posible usar un polinomio algo diferente para hacer esto, pero no lo he conseguido realmente. Voy a pensar en ello un poco más ....

basado parcialmente en this answer.

Answer 2

Tiene que ser al menos O (n^2), ya que hay n (n-1)/2 sumas diferentes posibles para verificar para otros miembros. Tienes que calcular todo eso, porque cualquier par sumado puede ser cualquier otro miembro (comienza con un ejemplo y permuta todos los elementos para convencerte de que todo debe ser verificado). O mira a fibonacci para algo concreto.

Así que al calcular eso y buscar miembros en una tabla hash se obtiene O (n^2) amortiguado. O utilice un árbol ordenado si necesita el peor de los casos.

Answer 3

Esencialmente necesita encontrar todas las diferentes sumas de pares de valores, así que no creo que se va a hacer nada mejor que O (n 2 ). Pero puede optimizar ordenando la lista y reduciendo los valores duplicados, y luego emparejando un valor con cualquier valor igual o mayor, y deteniéndose cuando la suma exceda el valor máximo en la lista.