Busqueda lineal y binaria
Páginas: 2 (397 palabras)
Publicado: 5 de marzo de 2012
BUSQUEDA LINEAL LIMLITADA SEGUN ORDEN RECURSIVA
La recursividad constituye una de las herramientasmas potentes en programacion.
Ventajas: No es necesario definir la secuencia de
pasos exactapara resolver el problema.
Desventajas: Podrıa ser menos eficiente.
Ejemplo: Calculo del factorial con n=3.
3! = 3 * 2!
3! = 3 * 2!
2! = 2 * 1!
3! = 3 * 2!
2! = 2* 1!
1! = 1 * 0!
3! = 3 * 2!
2! = 2 * 1!
1! = 1 * 0!
0! = 1(caso base)
3! = 3 * 2!
2! = 2 * 1!
1! = 1 * 1
1
3! = 3 * 2!
2! = 2 * 11! = 1 * 1 = 1
3! = 3 * 2
2! = 2 * 1 = 2
3! = 3 * 2 = 6
Para resolver un problema
Tendremos que diseñar: casos base, casosgeneralesy la solucion en terminos de ellos.
Casos base: Son los casos del problema que se resuelve con un segmento de código sin recursividad.
Los casos generales siempre deben avanzar hacia un caso base.Es decir, la llamada recursiva se hace a un sub. problemas mas pequeño y, en ultima instancia, los casos generales alcanzaran un caso base.
BUSQUEDA BINARIA ITERATIVA
La búsqueda binariaconsiste en dividir el array por su elemento medio en dos subarrays más pequeños, y comparar el elemento con el del centro.
Si coinciden, la búsqueda se termina. Si el elemento es menor, debe estar (siestá) en el primer subarray, y si es mayor está en el segundo.
La búsqueda binaria divide el espacio de búsqueda cada vez a la mitad, comportándose de la siguiente manera: n, n/2, n/4, n/8, n/16...esta serie tiene un comportamiento logarítmico, por lo cual el ciclo en el peor de los casos se realizará cuantas veces sea necesario hacer para encontrar el numero.
Por ejemplo, para buscar...
La recursividad constituye una de las herramientasmas potentes en programacion.
Ventajas: No es necesario definir la secuencia de
pasos exactapara resolver el problema.
Desventajas: Podrıa ser menos eficiente.
Ejemplo: Calculo del factorial con n=3.
3! = 3 * 2!
3! = 3 * 2!
2! = 2 * 1!
3! = 3 * 2!
2! = 2* 1!
1! = 1 * 0!
3! = 3 * 2!
2! = 2 * 1!
1! = 1 * 0!
0! = 1(caso base)
3! = 3 * 2!
2! = 2 * 1!
1! = 1 * 1
1
3! = 3 * 2!
2! = 2 * 11! = 1 * 1 = 1
3! = 3 * 2
2! = 2 * 1 = 2
3! = 3 * 2 = 6
Para resolver un problema
Tendremos que diseñar: casos base, casosgeneralesy la solucion en terminos de ellos.
Casos base: Son los casos del problema que se resuelve con un segmento de código sin recursividad.
Los casos generales siempre deben avanzar hacia un caso base.Es decir, la llamada recursiva se hace a un sub. problemas mas pequeño y, en ultima instancia, los casos generales alcanzaran un caso base.
BUSQUEDA BINARIA ITERATIVA
La búsqueda binariaconsiste en dividir el array por su elemento medio en dos subarrays más pequeños, y comparar el elemento con el del centro.
Si coinciden, la búsqueda se termina. Si el elemento es menor, debe estar (siestá) en el primer subarray, y si es mayor está en el segundo.
La búsqueda binaria divide el espacio de búsqueda cada vez a la mitad, comportándose de la siguiente manera: n, n/2, n/4, n/8, n/16...esta serie tiene un comportamiento logarítmico, por lo cual el ciclo en el peor de los casos se realizará cuantas veces sea necesario hacer para encontrar el numero.
Por ejemplo, para buscar...
Leer documento completo
Regístrate para leer el documento completo.