¿Cuál es el método de fuerza bruta?

El método de fuerza bruta no utiliza ningún conocimiento adicional sobre el problema e intenta resolverlo de la manera “más simple”, que a menudo es muy lenta.

Por ejemplo, al descifrar la fuerza bruta del pin de su amigo significaría verificar todas las combinaciones posibles (suponemos que el pin tiene 4 dígitos y usa números del 0 al 9).

El enfoque de fuerza bruta de encontrar un elemento en la matriz significaría ir a través de la matriz hasta que vea el elemento. Tenga en cuenta que a veces si tiene un conocimiento adicional (por ejemplo, sabe que los números en la matriz están ordenados), puede usar un método más rápido.

Dejame darte un ejemplo. Digamos que queremos buscar un par que su suma sea igual a 111 en la siguiente matriz:

int [] a = {4,9,0,34,7,22,3,10,1,5,12,55,89,32,53,62};

Para hacerlo más corto, el par es 22 y 89. ¿Cómo encontrarlo?

El enfoque de la fuerza bruta es probar cada par:

clase pública FindPair {

par privado de clase estática {
public int x;
public int y;

@Anular
public String toString () {
return “[x =” + x + “, y =” + y + “]”;
}
}

public static void main (String [] args) {

int [] a = {4, 9, 0, 34, 7, 22, 3, 10, 1, 5, 12, 55, 89, 32, 53, 62};
int objetivo = 111;
Resultado del par = nuevo Par ();

for (int i = 0; i

para (int j = i + 1; j

if (a [i] + a [j] == objetivo) {
resultado.x = a [i];
resultado.y = a [j];
rotura;
}

}

}

System.out.println (“par = [” + resultado + “]”);
}
}

Funciona, pero el tiempo de ejecución es O (n2), porque tengo que revisar todos los elementos cada vez que quiero comparar un nuevo par. Ver :

Análisis de algoritmos

Notación O grande – Wikipedia

Una forma más eficiente es buscar es ordenar nuestra matriz:

public static void main (String [] args) {

int [] a = {4, 9, 0, 34, 7, 22, 3, 10, 1, 5, 12, 55, 89, 32, 53, 62};
Arreglos.sort (a);
int objetivo = 111;
Resultado del par = nuevo Par ();

for (int i = 0; i

int j = Arrays.binarySearch (a, target – a [i]);

si (j> = 0) {
resultado.x = a [i];
resultado.y = a [j];
rotura;
}

}

System.out.println (“par = [” + resultado + “]”);
}

Es mejor, ya que podemos hacerlo en O (n log n) ya que estamos ordenando la matriz. Pero podemos hacerlo aún mejor … puedo usar una tabla hash para verificar los valores que he visto y compararlos con los que tengo ahora …

public static void main (String [] args) {

int [] a = {4, 9, 0, 34, 7, 22, 3, 10, 1, 5, 12, 55, 89, 32, 53, 62};
int objetivo = 111;
Resultado del par = nuevo Par ();
Establecer set = new HashSet <> ();

for (int i = 0; i

if (set.contains (target – a [i])) {
resultado.x = objetivo – a [i];
resultado.y = a [i];
rotura;
}
set.add (a [i]);

}

System.out.println (“par = [” + resultado + “]”);
}

Ahora hemos terminado nuestro trabajo con el tiempo O (n) y el Espacio O (n).

Intentando combinaciones una y otra vez hasta que algo funciona. Muy simple y que consume mucho tiempo sin una gran cantidad de poder de procesamiento

Significa probar todas las soluciones posibles en el espacio de búsqueda y elegir solo las soluciones correctas.