Algoritmo De Fuerza Bruta

603 palabras 3 páginas
Tema:
Algoritmo de Fuerza Bruta

Realizado por:
Bryan Alba
Lourdes Fárez

Facultad:
Ingeniería

Escuela:
Informática

Materia:
Programación 2
Estructura de Datos y Análisis de Algoritmos

Profesor:
Ing. Malhena Sánchez

Fecha:
30 de Octubre 2012

ALGORITMO DE FUERZA BRUTA
Introducción:
Los algoritmos de Fuerza Bruta son capaces de encontrar la solución a cualquier problema por complicado que sea. Su fundamento es muy simple, probar todas las posibles combinaciones, recorrer todos los caminos hasta dar con la situación que es igual que la solución. No le importa iniciar caminos malos o muy malos, al llegar a su final y ver que su destino no es la solución, se iniciará otro camino en busca del que conduzca a ella.
…ver más…
* Para la búsqueda: * Consiste en la comparación de todas las posiciones del texto entre 0 y el n-m, si una ocurrencia del patrón corresponde o no. * Si encuentra una no ocurrencia, o una ocurrencia total del patrón, salta un carácter hacia la derecha.
Ejemplo:
Se alinea la primera posición del patrón con la primera posición del texto, y se comparan los caracteres uno a uno hasta que se acabe el patrón, esto es, se encontró una ocurrencia del patrón en el texto, o hasta que se encuentre una discrepancia.

Si se detiene la búsqueda por una discrepancia, se desliza el patrón en una posición hacia la derecha y se intenta calzar el patrón nuevamente.

Análisis de Complejidad (Costes): * En el mejor caso, el primer elemento del patrón no está en el texto, de manera que ningún carácter coincide con él. Tenemos un coste temporal de orden O(n), el algoritmo es lineal. * En el peor caso el coste temporal de este algoritmo es de O(mn), que sería aquel en el que encontramos el patrón en todas las subcadenas del texto. * En promedio el coste temporal es menor que O(mn), ya que no precisamos comparar cada vez los m caracteres, sólo comparamos hasta que se detecta un fallo y las probabilidades de falsos comienzos son muy inferiores a 1 en general. Si buscamos en textos normales será de orden O(m+n) en la mayoría de los casos. * El coste espacial es nulo, salvo que consideremos

Documentos relacionados

  • Analisis De La Lectura Piedra Bruta
    1749 palabras | 7 páginas
  • Historia de los algoritmos
    3340 palabras | 14 páginas
  • ejemplos de algoritmos secuenciales
    653 palabras | 3 páginas
  • Algoritmo De Ordenamiento Externo
    805 palabras | 4 páginas
  • Métodos para solución de problemas con algoritmos
    1261 palabras | 6 páginas
  • Ejercicios De Algoritmo
    749 palabras | 4 páginas
  • EJERCICIOS DE ALGORITMOS SECUENCIALES
    1383 palabras | 6 páginas
  • Algoritmo de fracciones
    726 palabras | 3 páginas
  • Las Brutas De Juan Radrigán.
    6650 palabras | 27 páginas