Si se nos da un conjunto ordenado de n números, ¿cómo encuentra un algoritmo theta (n) que dado otro número x, determina si existen dos elementos en el conjunto de entrada cuya suma es exactamente x?

Answer 1

Deje que [math] a_1 \ leq a_2 \ leq \ ldots \ leq a_n [/ math] sean los elementos en la matriz.

Tenga en cuenta que dados dos elementos [math] a_i \ leq a_j [/ math] si tenemos

[matemática] a_i + a_j <x [/ matemática] podemos aumentar la suma tomando [matemática] a_ {i + 1} [/ matemática] en lugar de [matemática] a_i [/ ​​matemática]

[math] a_i + a_j> x [/ math] podemos disminuir la suma tomando [math] a_ {j-1} [/ math] en lugar de [math] a_j [/ math]

Además, si

[matemática] a_i + a_j <x [/ matemática] para todos [matemática] k \ leq i [/ matemática] tenemos que [matemática] a_k + a_j <x [/ matemática]

[matemática] a_i + a_j> x [/ matemática] para todos [matemática] k \ geq j [/ matemática] tenemos que [matemática] a_i + a_k> x [/ matemática]

De esta manera, podemos evitar mirar cada par porque podemos identificar pares “malos” mirando solo uno de ellos.

Con eso en mente, el siguiente pseudocódigo resuelve el problema

i = 0, j = n-1
mientras que (i <= j) {
if (a [i] + a [j] == x) devuelve verdadero // ¡Solución encontrada!
if (a [i] + a [j] <x) i = i + 1 // Incremente la suma
if (a [i] + a [j]> x) j = j-1 // Disminuye la suma
}
return false // No se encontró solución

La complejidad temporal de este algoritmo es [matemática] \ theta (n) [/ matemática] porque en cada iteración aumentamos [matemática] i [/ matemática] en [matemática] 1 [/ matemática] o disminuimos [matemática] j [ / math] por [math] 1 [/ math] y se detienen cuando se encuentran en el medio (o encontramos una solución). De esta forma, el aspecto se ejecutará la mayoría de las veces [math] n-1 [/ math] (y el costo de cada iteración es [math] \ theta (1) [/ math])

Answer 2

1. Comenzando desde el comienzo de la matriz ordenada, digamos que estamos en el índice ‘inicio’, de modo que para todos los números presentes antes de ‘inicio’ no hay ningún otro número en la matriz, por lo que la suma es igual a x.
2. Ahora intentamos encontrar un índice mayor que ‘inicio’, digamos ‘último’, de modo que la suma de los números en el índice ‘inicio’ y ‘último’ sea mayor que x y la suma de los números en el índice ‘inicio’ y ‘último’ -1 es menor que x. Obviamente, verificaremos la condición cuando los números en el índice ‘inicio’ y ‘último’ sean iguales a x, habríamos encontrado los dos elementos y saldríamos de nuestro algoritmo.
3. Ahora la condición es tal que para el número en el índice ‘inicio’ no tenemos ningún otro número tal que la suma sea x. Entonces tenemos que incrementar ‘inicio’ (déjenme llamarlo ‘nuevo comienzo’). El número en el índice ‘new-start’ es mayor que el número en el índice ‘start’, por lo que si lo agrega al número en el índice ‘last’, la suma sería mayor que x, por lo que no es necesario verificarlo. Esto también será cierto para los números sobre el índice ‘último’ también. Entonces, para encontrar lo que hacemos en el paso 2 anterior, ahora solo necesitamos verificar hacia abajo desde el índice ‘último’ – 1. Para iniciar el algoritmo ‘último’ se tomará como el final de la matriz ordenada.
4. Los pasos en 2 y 3 anteriores deben repetirse hasta que el índice ‘inicio’ sea mayor que el índice ‘actual’.

En los pasos anteriores cada vez que vamos al paso 2, el índice ‘inicio’ se ha incrementado o el índice ‘último’ se ha decrementado y el algoritmo termina cuando ‘inicio’ es mayor que ‘último’. Entonces, la complejidad del algoritmo es O (n).

Answer 3

Establece dos punteros, uno en xy otro en 0, y los une, por ejemplo, suponga a (19) = x, y a (0) = 1, esto es demasiado, por lo tanto disminuya 19 a a (18) etc. .

Answer 4

Deje que la matriz sea a_1, a_2, …, a_n en orden creciente. Deje b_i = a_ {ni}. Luego comience con a_1 y b_1.
Si a_1 + b_1 Si a_1 + b_1> x, reemplace b_1 con b_2
Si a_1 + b_1 = x, listo.

Seguir con
Si a_i + b_j Si a_i + b_j> x, reemplace b_j con b_ {j + 1}
Si a_i + b_j = x, listo.

Si no hay “hecho” hasta que i = no b = n, entonces no hay tales dos elementos.

Con suerte, esto es correcto.