Dadas [math] N [/ math] páginas de datos con la única operación permitida [math] query (i), [/ math] ¿qué algoritmo encuentra la última página usando la menor cantidad de consultas?

Answer 1

Supongamos que hay al menos 1 página, pero no sabemos nada sobre cuán grande puede ser [matemática] N [/ matemática].

Haremos una especie de búsqueda binaria inversa como primer paso y luego haremos una búsqueda binaria como segundo paso.

Comience con [matemáticas] i = 1 [/ matemáticas]. Si la consulta [matemática] (i) [/ matemática] no se encuentra, la última página es la página 0 y puede detenerse.

De lo contrario, duplique repetidamente i y ejecute [math] query (i) [/ math] hasta que no lo encuentren.

Ahora sabe que el último número de página debe estar entre [matemática] i / 2 [/ matemática] (resultado del paso anterior) y [matemática] i-1 [/ matemática]. Ahora puede ejecutar la búsqueda binaria para encontrar la última página.

Utilice [math] i / 2 [/ math] como límite inferior y [math] i-1 [/ math] como límite superior. Consulta la media aritmética de los límites. ¿Aún no se encuentra? Establezca el límite superior en la posición consultada menos 1. ¿Encontró en su lugar? Haga que la posición consultada sea el límite inferior. Repita hasta que el mínimo y el máximo se encuentren. Este es el número de la última página.

El número de pasos necesarios: [math] \ log_2 N [/ math] para encontrar el primer número de página fuera de rango, luego [math] \ left (\ log_2 N \ right) -1 [/ math] pasos para binario buscar. La complejidad del tiempo es, por lo tanto, [matemática] O (\ log N) [/ matemática].

Answer 2

Llamemos al algoritmo que verifica todos los índices desde [math] 0 [/ math] en adelante uno por uno [math] BRUTAL [/ math]. El punto sobre [matemática] BRUTAL [/ matemática] es que está garantizado encontrar [matemática] N [/ matemática] en la mayoría de los pasos [matemática] N + 1 [/ matemática].

Ahora considere la familia de algoritmos [math] TRICKY_i [/ ​​math] que hacen lo siguiente:

Primero realice la consulta [matemática] (i-1) [/ matemática]. Si esto falla, llame a [math] BRUTAL [/ math], de lo contrario realice la consulta [math] (i) [/ math]. Si esto falla, devuelva [math] i [/ math] como [math] N [/ math], de lo contrario llame a [math] BRUTAL [/ math].

[math] TRICKY_i [/ ​​math] puede encontrar [math] N [/ math] en [math] 2 [/ math] pasos si [math] N = i [/ math] y está garantizado que encuentra [math] N [/ matemática] como máximo en [matemática] N + 3 [/ matemática] pasos.

Suponga que existe un algoritmo que es óptimo para todas [matemáticas] N [/ matemáticas] y lo llama [matemáticas] OPT [/ matemáticas].

Porque para todos [matemáticas] N [/ matemáticas] hay un [matemáticas] TRICKY_N [/ matemáticas] que puede encontrar [matemáticas] N [/ matemáticas] en [matemáticas] 2 [/ matemáticas] pasos, [matemáticas] OPT [/ math] solo puede ser óptimo si encuentra [math] N [/ math] en a lo sumo [math] 2 [/ math] pasos para todos [math] N [/ math]. Esto es imposible por lo tanto [math] OPT [/ math] no existe.

Answer 3

No estoy seguro si el método dado en una respuesta anterior es pptimal

Sugeriría lo siguiente:

consulta (100 + 100xk) hasta que aparezca “la página no duda”.

consulta (100 + 100x k – 50):

si consigues la página no dudes

consulta (100 + 100x k – 50–25)

de otra manera

consulta (100 + 100x k – 50 + 25);

Los siguientes pasos tendrán 12 6 3 2 y 1.

El número máximo de consultas: es (6 + int (N / 100))

Es una tarea interesante y la estrategia óptima depende de cuán grande pueda ser N. En mi época, el número entero más grande era aproximadamente 34000 …