¿Cómo desarrollar un algoritmo resuelve el problema de 2 sumas?

Dado un conjunto ordenado de enteros, quiero encontrar el número de pares que suman $0$ . Por ejemplo, dado $\{-3,-2,0,2,3,4\}$ , el número de pares suma a cero es $2$ .

Sea $N$ el número de elementos en la matriz de entrada. Si uso la búsqueda binaria para encontrar el inverso aditivo para un elemento en la matriz, el orden es $O(\log N)$ . Si recorro todos los elementos del conjunto, entonces el orden es $O(N\log N)$ .

¿Cómo encontrar un algoritmo de orden $O(N)$ ?

algorithms Laura
fuente

El problema

k

$k$ -SUM generalmente se refiere a un problema ligeramente diferente, donde uno trata de encontrar un conjunto de

k

$k$ elementos de la matriz de entrada

A

$A$ modo que sumen cero. En cierto modelo de computación, es imposible obtener un algoritmo de tiempo lineal para

k = 2

$k=2$ , o para cualquier

par

k

$k$ . Ver esta pregunta .

Juho

Respuestas:

Deje ser la matriz de entrada ordenada. Mantener dos punteros y que ir a través de los elementos en . El puntero pasará por la "parte izquierda" de , que son los enteros negativos. El puntero hace lo mismo para la "parte correcta", los enteros positivos. A continuación, describiré una solución de pseudocódigo y supondré que por simplicidad menor. Omitido son también los controles para los casos en que no sólo son positivas o negativas sólo enteros en . $A$ $l$ $r$ $A$ $l$ $A$ $r$ $0 \notin A$ $A$

COUNT-PAIRS(A[1..N]):
 l = index of the last negative integer in A
 r = index of the first positive integer in A
 count = 0;

 while(l >= 0 and r <= N)
   if(A[l] + A[r] == 0)
     ++count; ++right; --left; continue;

   if(A[r] > -1 * A[l]) 
     --left;
   else 
     ++right;

Es obvio que el algoritmo toma tiempo . $O(N)$

Juho
fuente

Probablemente debería agregar un argumento para la corrección.

Raphael

-1

El enfoque más simple, según tengo entendido, parece ser utilizar una tabla hash, H = {a [0] = verdadero, .., a [n-1] = verdadero}. Esta tabla hash se puede construir en tiempo O (n). Una vez que se construye la tabla hash, repita a través de A [0, .., n-1] y verifique si H [-1 * a [i]] existe. Si lo hace, incremente un contador en 1 y devuelva el resultado final. Esto es claramente O (n).

Juspreet Sandhu
fuente

Las expresiones H = {a [0] = verdadero, .., a [n-1] = verdadero} y A [0, .., n-1] no tienen ningún sentido para mí. Cuando se utiliza una función hash, la matriz ni siquiera debe clasificarse. Pero los algoritmos que usan la función hash usan algunas propiedades pseudoaleatorias de la función hash. En el peor de los casos, todos los elementos se asignarán al mismo valor hash y el algoritmo es cuadrático. No sé cuáles son los requisitos del OP.

miracle173

Vea mi implementación de esto a continuación y dígame cómo es cuadrático en el peor de los casos.

sammy

@ miracle173: Eso es solo conveniencia para la notación. Puedo representar la tabla hash como un conjunto de pares clave-valor (que es lo que realmente es, matemáticamente hablando). La disposición real en la memoria es innecesaria para los detalles teóricos con respecto a la complejidad. Y, las funciones de hash están diseñadas para evitar colisiones, siempre que haya suficiente entropía de semillas. Respondí con el porque la respuesta de Juho supone una "A ordenada", que implícitamente hace que la complejidad sea O (n log (n)) y * NO O (n).

Juspreet Sandhu

@ manbearpig1 User Evil ya agregó un comentario a su publicación que debería responder a su pregunta. El peor caso de la búsqueda de la tabla hash es O (n) y, por lo tanto, el peor caso de todo el algoritmo es O (n ^ 2).

miracle173

@JuspreetSandhu Usere Evil agregó un comentario a otra respuesta que explicaba el problema con las funciones hash.

miracle173

-1

Tenga en cuenta que podemos buscar un valor en un conjunto de Python en tiempo constante.

def twoSum(data):
    count = 0
    nums = set()
    for num in data:
        if (num * -1) in nums:
            count += 1
        nums.add(num)
    return count

sammy
fuente

No es tiempo constante, sino tiempo constante esperado. Puede haber una tabla hash, un árbol (auto) equilibrado o una estructura similar. Esto proporciona esperado pero puede ser en caso degradado para la tabla hash o para el árbol. Además, aquí preferimos el pseudocódigo porque no todos entienden Python, por lo que no es obvio por qué o cómo funciona. En el peor de los casos para la tabla hash donde cada valor se mapea en un bin, el tiempo para obtener el elemento es . Realiza este paso veces, por lo que da en el peor de los casos.

O (1)

$\mathcal O(1)$

O (n)

$\mathcal O(n)$

O (\log n)

$\mathcal O(\log n)$

O (n)

$\mathcal O(n)$

n

$n$

O (n^{2})

$\mathcal O(n^2)$

Evil