Scribd
Cargar
67 vistas3 páginas

Comparación de Búsquedas Exponenciales

El documento describe los casos mejor, peor y promedio de un algoritmo de búsqueda exponencial. En el mejor caso, el elemento se encuentra en el primer índice con 1 comparación. En el peor caso, se realizan log2n comparaciones dentro de un ciclo while y luego log2(n-1)/2 comparaciones de búsqueda binaria. La función para el peor caso es f(n)=log2n + log2(n-1)/2 + 1.

Cargado por

Denisse Márquez Morales
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd
67 vistas3 páginas

Comparación de Búsquedas Exponenciales

El documento describe los casos mejor, peor y promedio de un algoritmo de búsqueda exponencial. En el mejor caso, el elemento se encuentra en el primer índice con 1 comparación. En el peor caso, se realizan log2n comparaciones dentro de un ciclo while y luego log2(n-1)/2 comparaciones de búsqueda binaria. La función para el peor caso es f(n)=log2n + log2(n-1)/2 + 1.

Cargado por

Denisse Márquez Morales
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd

Búsqueda exponencial

1 comparación Mejor caso

Comparaciones

Peor caso

Comparación

Operaciones básicas
Comparación del if (para el mejor caso); las comparaciones del while y las de la búsqueda binaria,
para el peor y caso medio.
Mejor caso
Es fácil notar que el mejor caso se presentará cuando el número a buscar se encuentra en el primer
índice del arreglo.

f t ( n )=1
Peor Caso
En el peor caso se presenta cuando el número se encuentra hasta el final del arreglo. Por ejemplo, se
tiene la siguiente instancia:
Índice 0 1 2 3 4 5 6 7
2 1 n=8
Valor 10 20 25 30 36 40
5
Se busca 40 en el arreglo.
Inicia el algoritmo y realiza una primera comparación para verificar si el número a buscar esta en el
primer índice del arreglo.
2 ≠ 40 → No se cumple

i=110 ≤ 40 → se cumplei=215 ≤ 40 → se cumplei=424 ≤ 40 → se cumple


i=8 → Ya se sale del rango del arreglo

MIN ( i , ( n−1 )) =MIN ( 8 , ( 8−1 ) )=MIN ( 8,7 ) =7 Como la búsqueda binaria el peor caso es log 2 n,
sin embargo, la n para la búsqueda exponencial se reduce a un rango que va desde la i valida dentro
del arreglo, hasta el extremo del arreglo. Entonces, para determinar el tamaño del arreglo que se
pasa a la búsqueda binaria, empezaremos por obtener el inicio, para el cual, se utilizará el número
de comparaciones – 1, por la que no se cumplió quedando la expresión en 2¿¿ ¿, ahora para obtener
los elementos del nuevo arreglo se supone que se busca el mínimo entre la última i obtenida y el
limite del arreglo, pero como se planteó que el peor caso es buscar el elemento en el extremo del
arreglo, se tiene que el número de elementos es ( n−1 )−¿ ¿), y aplicando el peor caso de la
búsqueda binaria, la expresión queda como, log 2 ¿ ¿, simplificando la expresión mediante
propiedades de logaritmos, la expresión para la búsqueda binaria que se hace dentro de la
n
exponencial del peor caso es log 2 −1. Sumando las expresiones obtenidas previamente son 1
2
n
(comparación) + log 2 n+1 (comparaciones dentro del ciclo while) + log 2 −1 (comparaciones
2
dentro de la búsqueda binaria). La función para el peor caso de la búsqueda exponencial es:
n
f t ( n )=log 2 n+ log 2 +1
2

Punto 4

Punto 5

Punto 7

Punto 9

También podría gustarte