¿Cuál es la complejidad temporal del algoritmo de búsqueda binaria?

Mientras que la búsqueda binaria en una función monotónica, el espacio de búsqueda se reduce a la mitad en cada iteración. El número de pasos es logarítmico, pero también debe considerar la complejidad de la función de predicado utilizada para mover punteros bajos y altos en cada iteración.

Echemos un vistazo al algoritmo de búsqueda binaria general donde el predicado p (x) es una función booleana. Supongamos que p (bajo) = FALSO y p (alto) = VERDADERO. (Este es el bucle invariante).

mientras que bajo y alto no se encuentran:
medio = (bajo + alto) / 2
si p (mid) es verdadero: high = mid
más: bajo = medio

En caso de búsqueda binaria en una matriz, el predicado puede ser p (x) = (x <= clave) (en el caso de la función lower_bound en C ++ STL). Su complejidad de tiempo es [matemáticas] O (1) [/ matemáticas]. Por lo tanto, la complejidad general es [matemática] O (log N) [/ matemática].

¿Qué sucede si la función de predicado tarda [matemáticas] O (N) [/ matemáticas] en tiempo? Entonces la complejidad es [matemática] O (N log (N)) [/ matemática]. Como puede ver, también depende de la complejidad de la función predicado. En general, si la complejidad de p (x) es [matemática] O (f (n)) [/ matemática], entonces la búsqueda binaria que usa necesita tiempo [matemática] O (f (n) * log (N)) [ /mates].

Nota:

1. N es el tamaño del espacio de búsqueda que se está considerando.
2. Supuse que las estructuras de datos en las que se realiza la búsqueda binaria, el acceso aleatorio requiere tiempo constante (como en las matrices).
3. Supuse que la implementación de búsqueda binaria es correcta. Esta es una lectura interesante: ¿cuáles son las trampas en la implementación de la búsqueda binaria? Lee la segunda respuesta de ShreevatsaR.

La complejidad temporal de cualquier algoritmo es una función [matemática] f (n) [/ matemática] que indica cuántos pasos de ejecución deben realizarse para llegar a la respuesta (finalizar el cálculo). El argumento [math] n [/ math] es el tamaño de la entrada.

En caso de búsqueda binaria, n es el tamaño de la matriz o el número de elementos en el espacio de búsqueda. [math] f (10) [/ math] debería darle el número de pasos que se ejecutarán si está buscando en una matriz de tamaño [math] 10 [/ math].

Ya puedes ver algunos defectos en la definición. El número de pasos ejecutados para la búsqueda binaria no solo depende del tamaño de la matriz ([math] n [/ math]), sino del elemento particular que se busca.

Para evitar esto, f generalmente se hace para representar la complejidad de tiempo del peor de los casos, que es el número máximo de pasos ejecutados para cualquier entrada, en función de [math] n [/ math].

En caso de búsqueda binaria, estos son pasos ejecutados para búsqueda fallida (¿encontrar por qué?).

Lea el algoritmo de búsqueda binaria antes de seguir leyendo .

Una búsqueda binaria fallida procede de la siguiente manera.

Matriz de tamaño n, verifique el elemento central (1 operación). Continúa la búsqueda en una de las partes dependiendo de lo que sucedió en el medio.

[matemáticas] f (n) = 1 + f (\ frac {n} {2}) [/ matemáticas]

Si la matriz era de tamaño 1, y el elemento central es el único elemento que se verifica primero (1 operación) y no hay nada más que dividir más. Recuerde que estamos describiendo una búsqueda fallida.

[matemáticas] f (1) = 1 [/ matemáticas]

Resolver las ecuaciones da

[matemáticas] f (n) = 1 + 1 + 1…. + 1 + f (\ frac {n} {2 ^ k}) [/ matemáticas]

Poner [matemáticas] \ frac {n} {2 ^ k} = 1 [/ matemáticas] da [matemáticas] k = \ log n [/ matemáticas] y [matemáticas] f (\ frac {n} {2 ^ k}) = f (1) = 1 [/ matemáticas]

Entonces [matemáticas] f (n) = \ log n +1 [/ matemáticas]

Cuál es la complejidad de la búsqueda binaria.

No todos los algoritmos tienen ecuaciones agradables que se puedan resolver fácilmente. Entonces decimos [math] f (n) [/ math] como complejidad asintótica del peor de los casos. Eso es otra cosa …

~ nD

O (log n).

Básicamente, mira el tamaño de su entrada ( matriz ordenada ), luego sigue dividiendo por dos y buscando en el medio hasta encontrar o llegar al final de la matriz.

Algoritmo de búsqueda binaria – Wikipedia

EDITAR:
Código fuente: BinarySearch.java

Coursera:

Algoritmos, Parte I | Coursera

Algoritmos, Parte II | Coursera

Libro (s):

Mi preferencia personal -> https://www.amazon.com/Algorithm …

Muy bien, pero mucha matemática: https://www.amazon.com/Introduct …

Muy bien también: https://www.amazon.com/Algorithm …

Es [matemáticas] O (logN) [/ matemáticas]. Si realiza una búsqueda binaria en una matriz de tamaño [matemática] N [/ matemática], tomará [matemática] O (logN) [/ matemática] tiempo en completarse. La búsqueda binaria se realiza dividiendo la matriz existente por la mitad. Por lo tanto, cada vez que llama a la subrutina (o completa una iteración), el tamaño se reduce a la mitad de la parte existente. Primero [matemática] N [/ matemática] se convierte en [matemática] N / 2 [/ matemática], luego se convierte en [matemática] N / 4 [/ matemática] y continúa hasta que encuentra que el elemento o tamaño se convierte en 1. Por lo tanto, no de iteración es [math] logN [/ math] (base 2).

Derivemos una recurrencia que podamos usar para determinar la complejidad de la búsqueda binaria en el peor de los casos. Denotemos [math] T (n) [/ math] como el número de comprobaciones que realiza la búsqueda binaria para elementos [math] n \ in \ mathbb {Z} ^ + [/ math]. En el peor de los casos, no se encuentra ningún elemento. Para facilitar nuestro análisis, suponga que [math] n [/ math] es una potencia de 2.

Cuando solo hay 1 entrada, hay una comprobación (ya sea que esté allí o no), por lo que [math] T (1) = 1. [/ Math]

A continuación, ¿qué hace la búsqueda binaria?

• Calcula la entrada del medio y luego (la verifica , si hay una coincidencia devuelve el índice, si no) reduce a la mitad el rango que verifica actualizando los límites superior e inferior para que los elementos [matemáticos] n / 2 [/ matemáticos] estén en el rango
• solo verificamos una de las dos mitades (una llamada recursiva). Esto se hace recursivamente hasta que se cruzan los límites superior e inferior (es decir, queda 1 entrada).

Entonces esto nos da la siguiente relación de recurrencia:

[matemática] T (n) = T (n / 2) + 1 [/ matemática], [matemática] T (1) = 1 [/ matemática].

Entonces, para determinar el comportamiento en el peor de los casos de la búsqueda binaria, solo necesitamos descubrir el comportamiento asintótico de [math] T (n) [/ math]. Puedo dejar que descubras este paso, pero invocaré una de las versiones más conocidas del teorema maestro: Wikipedia. Tenga en cuenta que en esta versión del Master Theorem puede ignorar las funciones de piso y techo en la parte recursiva de la relación.

El teorema maestro: Wikipedia dice [matemáticas] T (n) \ in \ Theta (\ log_2 {n}). [/ Matemáticas]

¡Espero que esto ayude!

La complejidad de tiempo de la búsqueda binaria es O (Log (n)) * A la base 2 *

Considere este algoritmo;

Algoritmo BinSearch (a, i, l, x)

/ * Tiene una matriz de elementos [i: l] en un orden no decreciente, debe determinar si ‘x’ existe en su matriz * /

si (l = i) entonces

{

if (x = a [i]) devuelve i;

de lo contrario, devuelve 0;

}

más

{

// reduce p en subproblemas más pequeños

mid = (mid + 1) / 2;

if (x = a [mid]) entonces devuelve mid;

si if (x

devolver BinSearch (a, i, mid-1, x)

más

volver BinSearch (a, mid + 1, l, x)

}

Aquí, si su problema era de tamaño N, se dividiría en tamaño N / 2 y luego N / 4 y así sucesivamente hasta que alcance el valor que está buscando.

El número máximo de divisiones es LogN.

La complejidad temporal del algoritmo de búsqueda binaria es O (log2 (N)).

De un vistazo, la tabla de complejidad es así:

Peor desempeño del caso: O (log2 n)

Mejor rendimiento del caso: O (1)

Rendimiento promedio del caso: O (log2 n)

Peor complejidad de espacio de caso: O (1)

Pero ese no es el hecho, el hecho es ¿por qué es log2 (N)?

Aquí hay una prueba matemática que describe por qué la complejidad es log2 (N).

La pregunta es, ¿cuántas veces puedes dividir N entre 2 hasta que tengas 1? Esto es esencialmente decir, haga una búsqueda binaria (la mitad de los elementos) hasta que lo encuentre. En una fórmula esto sería esto:

1 = N / 2x

multiplicar por 2x:

2x = N

ahora haz el log2:

log2 (2x) = log2 N

x * log2 (2) = log2 N

x * 1 = log2 N

Esto significa que puede dividir el registro N veces hasta que haya dividido todo. Lo que significa que debe dividir el log N (“hacer el paso de búsqueda binaria”) hasta que encuentre su elemento.

La complejidad temporal se calcula para tres casos.
1 Mejor caso: 0 (1). – cuando el elemento que buscamos presente en el principio.
2. Peor caso: 0 (logn) – cuando el elemento presente en el último.
3. Caso promedio: 0 (logn): cuando el elemento está presente en el medio o en el medio.

La búsqueda binaria divide la lista ordenada en dos y registra solo uno de ellos

Por lo tanto, recurrencia: T (n) = T (n / 2) +1 que nos da la complejidad O (log n)

La búsqueda binaria se realiza dividiendo la matriz existente por la mitad. Por lo tanto, cada vez que llama a la subrutina (o completa una iteración), el tamaño se reduce a la mitad de la parte existente. Primero N se convierte en N / 2, luego se convierte en N / 4 y continúa hasta que encuentra que el elemento o el tamaño se convierten en 1.