Gallop ¿Complejidad del tiempo de búsqueda?

Question

Gallop search es para buscar un elemento en una lista ordenada. Empiezas a tomar un elemento en el índice 0, luego en el índice 1, 2, 4, 8, 16, etc. hasta que rebasas tu objetivo, y luego vuelves a buscar en el rango que acabas de encontrar.

¿Cuál es la complejidad del tiempo de esto? Me parece que es una especie de complejidad de tiempo logarítmico, pero no puedo entender qué.

Answer 1

(Véase mi EDITAR abajo)

Veamos el comportamiento peor de los casos. la búsqueda continúa desde 0, 1, 2, 4, 8 .... digamos que n es 2^k para algunos k> = 0. en el peor de los casos, podríamos terminar buscando hasta 2^k y darnos cuenta de que pasamos de largo objetivo. Ahora sabemos que el objetivo puede estar en 2^(k - 1) y 2^k. La cantidad de elementos en ese rango son 2^(k - 1) (piense un segundo). La cantidad de elementos que hemos examinado hasta ahora es O (k) que es O (logn). La siguiente repetición lo resume.

T(n) = T(n/2) + O(logn) 
    = T(n/4) + c1log(n/2) + c2logn ((all logs are base 2.)) 
    . 
    . 
    . 
    . 
    = O((logn)^2) 

Por lo que la complejidad del caso más desfavorable de este algoritmo es cuadrática de logn. Tal vez no sea el límite más estricto, pero es un buen límite superior.

EDIT: Estoy equivocado. He tomado la definición de búsqueda de galope dada aquí literalmente sin seguir el enlace. El enlace dice, una vez que rebasamos, hacemos una búsqueda binaria en el intervalo anterior. Se necesita tiempo de registro (n) para rebasar el objetivo y registrar (n) el tiempo para realizar búsquedas binarias en el intervalo ordenado. Esto lo convierte en el algoritmo O (log (n)). Gracias a Sumudu Fernando por señalarlo en los comentarios. Lo aprecio.