Cómo calcular la complejidad de búsqueda binaria

144

Escuché a alguien decir que dado que la búsqueda binaria reduce a la mitad la entrada requerida para buscar, por lo tanto, es el algoritmo log (n). Como no soy de un entorno matemático, no puedo relacionarme con él. ¿Alguien puede explicarlo con un poco más de detalle? ¿Tiene que ver algo con la serie logarítmica?

Conejo conejo
fuente
1
esto podría ayudarlo: stackoverflow.com/a/13093274/550393
2cupsOfTech

Respuestas:

385

Aquí una forma más matemática de verlo, aunque no es realmente complicado. OMI mucho más claro que los informales:

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 / 2 x

multiplicar por 2 x :

2 x = N

ahora haz el log 2 :

log 2 (2 x ) = log 2 N
x * log 2 (2) = log 2 N
x * 1 = log 2 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.

duedl0r
fuente
acabo de calcularlo en t (n) = (2 ^ 2) * K. ¿Cómo hacer que se registre el formulario?
Shan Khan
1
el mismo concepto explicado gráficamente: stackoverflow.com/a/13093274/550393
2cupsOfTech
La parte que me falta es, si tiene un BST con 7 entradas, ¿cuál es su fórmula? log2 (7)? Hice un cálculo de la fuerza bruta con cada resultado posible y llegué a una respuesta que no era igual a log2 (7), entonces, ¿qué estoy haciendo mal?
Perry Monschau
1
Mucho más fácil que la explicación del árbol binario.
NoName
1
Muy buena respuesta
VHS
22

Para la búsqueda binaria, T (N) = T (N / 2) + O (1) // la relación de recurrencia

Aplicar el teorema de Masters para calcular la complejidad del tiempo de ejecución de las relaciones de recurrencia: T (N) = aT (N / b) + f (N)

Aquí, a = 1, b = 2 => log (a base b) = 1

Además, aquí f (N) = n ^ c log ^ k (n) // k = 0 & c = log (a base b)

Entonces, T (N) = O (N ^ c log ^ (k + 1) N) = O (log (N))

Fuente: http://en.wikipedia.org/wiki/Master_theorem

abstractKarshit
fuente
1
¿Por qué log (a base b) es 1 cuando a = 1 y b = 2, ¿no debería ser 0?
GAURANG VYAS
16

T (n) = T (n / 2) +1

T (n / 2) = T (n / 4) + 1 + 1

Pon el valor de The (n / 2) arriba para que T (n) = T (n / 4) + 1 + 1. . . . T (n / 2 ^ k) + 1 + 1 + 1 ..... + 1

= T (2 ^ k / 2 ^ k) + 1 + 1 .... + 1 hasta k

= T (1) + k

Como tomamos 2 ^ k = n

K = log n

Entonces la complejidad del tiempo es O (log n)

Dhiren Biren
fuente
10

No hace la mitad del tiempo de búsqueda, eso no lo haría iniciar sesión (n). Lo disminuye logarítmicamente. Piensalo por un momento. Si tuviera 128 entradas en una tabla y tuviera que buscar su valor linealmente, probablemente tomaría alrededor de 64 entradas en promedio para encontrar su valor. Eso es n / 2 o tiempo lineal. Con una búsqueda binaria, elimina la mitad de las posibles entradas en cada iteración, de modo que a lo sumo solo tomaría 7 comparaciones para encontrar su valor (la base de registro 2 de 128 es 7 o 2 a la potencia de 7 es 128). El poder de la búsqueda binaria.

Michael Dorgan
fuente
Perdón por el necropost, pero 128 no es un árbol lleno de manera uniforme. Utilicé un ejemplo básico para entender esto, y descubrí que 7 entradas llenan uniformemente un árbol con 3 capas. Calculé que la complejidad debería ser 17/7 (la media de la suma total de comparaciones) que es 2.43. Pero log2 (7) es 2,81. Entonces, ¿qué me estoy perdiendo aquí?
Perry Monschau
Dos respuestas: la primera aquí: incluso si no hay ningún error en las matemáticas, podemos ver que el promedio de 2.43 sigue siendo mejor que el promedio de 3.5 para lineal, y esto tiene un valor bajo. Una vez que entras en los cientos de entradas, log2 () es mucho mejor que lineal. Sin embargo, creo que ves esto, así que a continuación.
Michael Dorgan
1
Segunda respuesta: No estoy seguro de qué tipo de árbol tienes donde 7 tiene todo lleno. Cuando pienso en un árbol perfecto de 8 entradas, veo un árbol profundo de 3 niveles con 8 hojas en total. En este árbol, no importa qué número busque, se necesitan 3 comparaciones totales para llegar de raíz a hoja. Para 7 entradas, una de las rutas tomaría una comparación menos, por lo que 20/7 (6 nodos de 3 compara, 1 nodo de 2 compara) que es ~ 2.85. Log2 (7) es ~ 2.81. No tengo los antecedentes matemáticos para explicar la diferencia de .04, pero supongo que tiene que ver con no tener bits fraccionales disponibles o alguna otra magia :)
Michael Dorgan
¿El número es el número de hojas? ¿No es el número de nodos? Bueno, esa era una gran información que me faltaba ... Me parece extraño que la función se base en hojas, cuando cada nodo de ramificación también es un punto de parada potencial. Bueno, de todos modos, ¡gracias por enderezar eso para mí!
Perry Monschau
5

La complejidad temporal del algoritmo de búsqueda binaria pertenece a la clase O (log n). Esto se llama notación O grande . La forma en que debe interpretar esto es que el crecimiento asintótico del tiempo que tarda la función en ejecutarse dado un conjunto de entrada de tamaño n no excederá log n.

Esto es solo jerga matemática formal para poder probar declaraciones, etc. Tiene una explicación muy sencilla. Cuando n crece mucho, la función log n aumentará el tiempo que lleva ejecutar la función. El tamaño del "conjunto de entrada", n, es solo la longitud de la lista.

En pocas palabras, la razón por la que la búsqueda binaria está en O (log n) es que reduce a la mitad el conjunto de entrada en cada iteración. Es más fácil pensarlo en la situación inversa. En iteraciones x, ¿cuánto tiempo puede examinar el algoritmo de búsqueda binaria en max? La respuesta es 2 ^ x. De esto podemos ver que lo contrario es que, en promedio, el algoritmo de búsqueda binaria necesita log2 n iteraciones para una lista de longitud n.

Si por qué es O (log n) y no O (log2 n), es porque simplemente ponlo de nuevo: el uso de las constantes de notación O grandes no cuenta.

vidstige
fuente
4

Aquí está la entrada de wikipedia

Si nos fijamos en el enfoque iterativo simple. Simplemente está eliminando la mitad de los elementos a buscar hasta que encuentre el elemento que necesita.

Aquí está la explicación de cómo se nos ocurre la fórmula.

Digamos inicialmente que tiene N número de elementos y luego lo que hace es ⌊N / 2⌋ como primer intento. Donde N es la suma del límite inferior y el límite superior. El primer valor de N sería igual a (L + H), donde L es el primer índice (0) y H es el último índice de la lista que está buscando. Si tiene suerte, el elemento que intenta encontrar estará en el medio [por ejemplo. Está buscando 18 en la lista {16, 17, 18, 19, 20} y luego calcula ⌊ (0 + 4) / 2⌋ = 2 donde 0 es el límite inferior (índice L del primer elemento de la matriz) y 4 es el límite superior (índice H del último elemento de la matriz). En el caso anterior, L = 0 y H = 4. Ahora 2 es el índice del elemento 18 que está buscando. ¡Bingo! Lo encontraste.

Si el caso fuera una matriz diferente {15,16,17,18,19} pero todavía estuvieras buscando 18, entonces no tendrías suerte y estarías haciendo primero N / 2 (que es ⌊ (0 + 4) / 2⌋ = 2 y luego se da cuenta de que el elemento 17 en el índice 2 no es el número que está buscando. Ahora sabe que no tiene que buscar al menos la mitad de la matriz en su próximo intento de buscar de forma iterativa. el esfuerzo de búsqueda se reduce a la mitad. Así que, básicamente, no busca la mitad de la lista de elementos que buscó anteriormente, cada vez que intenta encontrar el elemento que no pudo encontrar en su intento anterior.

Entonces el peor caso sería

[N] / 2 + [(N / 2)] / 2 + [((N / 2) / 2)] / 2 .....
es decir:
N / 2 1 + N / 2 2 + N / 2 3 + ..... + N / 2 x … ..

hasta que ... haya terminado de buscar, donde el elemento que está tratando de encontrar está al final de la lista.

Eso muestra que el peor de los casos es cuando alcanzas N / 2 x donde x es tal que 2 x = N

En otros casos, N / 2 x donde x es tal que 2 x <N El valor mínimo de x puede ser 1, que es el mejor de los casos.

Ahora, matemáticamente, el peor caso es cuando el valor de
2 x = N
=> log 2 (2 x ) = log 2 (N)
=> x * log 2 (2) = log 2 (N)
=> x * 1 = log 2 (N)
=> Más formalmente ⌊log 2 (N) + 1⌋

RajKon
fuente
1
¿Cómo se obtiene exactamente la versión más formal?
Kalle
Se utiliza una función de piso. Los detalles se encuentran en la sección de rendimiento del enlace wiki ( en.wikipedia.org/wiki/Binary_search_algorithm ) que se proporciona en la respuesta.
RajKon
2

Digamos que la iteración en Binary Search termina después de k iteraciones. En cada iteración, la matriz se divide por la mitad. Entonces, digamos que la longitud de la matriz en cualquier iteración es n En la iteración 1,

Length of array = n

En la iteración 2,

Length of array = n⁄2

En la iteración 3,

Length of array = (n⁄2)⁄2 = n⁄22

Por lo tanto, después de la iteración k,

Length of array = n⁄2k

Además, sabemos que después Después de divisiones k, la longitud de la matriz se convierte en 1 tanto

Length of array = n⁄2k = 1
=> n = 2k

Aplicando la función de registro en ambos lados:

=> log2 (n) = log2 (2k)
=> log2 (n) = k log2 (2)
As (loga (a) = 1)

Por lo tanto,

As (loga (a) = 1)
k = log2 (n)

Por lo tanto, la complejidad temporal de la búsqueda binaria es

log2 (n)
SirPhemmiey
fuente
1

Una búsqueda binaria funciona dividiendo el problema a la mitad repetidamente, algo como esto (detalles omitidos):

Ejemplo buscando 3 en [4,1,3,8,5]

  1. Ordene su lista de artículos [1,3,4,5,8]
  2. Mira el artículo del medio (4),
    • Si es lo que estás buscando, detente
    • Si es mayor, mira la primera mitad
    • Si es menos, mira la segunda mitad
  3. Repita el paso 2 con la nueva lista [1, 3], encuentre 3 y pare

Es un bi búsqueda -nary cuando se divide el problema en 2.

La búsqueda solo requiere pasos log2 (n) para encontrar el valor correcto.

Recomendaría Introducción a los algoritmos si desea aprender sobre la complejidad algorítmica.

Silas Parker
fuente
1

Dado que reducimos una lista a la mitad cada vez, por lo tanto, solo necesitamos saber en cuántos pasos obtenemos 1 a medida que dividimos una lista por dos. En el cálculo a continuación, x denota el número de veces que dividimos una lista hasta que obtenemos un elemento (en el peor de los casos).

1 = N / 2x

2x = N

Tomando log2

log2 (2x) = log2 (N)

x * log2 (2) = log2 (N)

x = log2 (N)

Abdul Malik
fuente
1

T (N) = T (N / 2) + 1

T (N) = T (N / 2) + 1 = (T (N / 4) + 1) + 1

...

T (N) = T (N / N) + (1 + 1 + 1 + ... + 1) = 1 + logN (base 2 log) = 1 + logN

Entonces, la complejidad temporal de la búsqueda binaria es O (logN)

TizeeU0U
fuente
0
ok see this
for(i=0;i<n;n=n/2)
{
i++;
}
1. Suppose at i=k the loop terminate. i.e. the loop execute k times.

2. at each iteration n is divided by half.

2.a n=n/2                   .... AT I=1
2.b n=(n/2)/2=n/(2^2)
2.c n=((n/2)/2)/2=n/(2^3)....... aT I=3
2.d n=(((n/2)/2)/2)/2=n/(2^4)

So at i=k , n=1 which is obtain by dividing n  2^k times
n=2^k
1=n/2^k 
k=log(N)  //base 2
Piyush Jain
fuente
0

Permítanme hacerlo fácil para todos ustedes con un ejemplo.

Para simplificar, supongamos que hay 32 elementos en una matriz en el orden ordenado en el que estamos buscando un elemento mediante la búsqueda binaria.

1 2 3 4 5 6 ... 32

Supongamos que estamos buscando 32. después de la primera iteración, nos quedaremos con

17 18 19 20 .... 32

después de la segunda iteración, nos quedaremos con

25 26 27 28 .... 32

después de la tercera iteración, nos quedaremos con

29 30 31 32

después de la cuarta iteración, nos quedaremos con

31 32

En la quinta iteración, encontraremos el valor 32.

Entonces, si convertimos esto en una ecuación matemática, obtendremos

(32 X (1/2 5 )) = 1

=> n X (2 -k ) = 1

=> (2 k ) = n

=> k log 2 2 = log 2 n

=> k = log 2 n

De ahí la prueba.

Sumukha HS
fuente
0

Aquí está la solución usando el teorema maestro, con LaTeX legible.

Para cada recurrencia en la relación de recurrencia para la búsqueda binaria, convertimos el problema en un subproblema, con tiempo de ejecución T (N / 2). Por lo tanto:

T (n) = T (n / 2) +1

Sustituyendo en el teorema maestro, obtenemos:

T (n) = aT (n / b) + f (n)

Ahora, como logbaes 0 yf (n) es 1, podemos usar el segundo caso del teorema maestro porque:

f (n) = O (1) = O (n0) = O (nlogba)

Esto significa que:

T (n) = O (nlogbalogn) = O (n0logn) = O (logn)

id01
fuente