algorithm - pseint - cómo calcular la complejidad de búsqueda binaria
busqueda binaria recursiva (9)
Escuché a alguien decir que dado que la búsqueda binaria reduce a la mitad la entrada requerida para buscar, entonces es el algoritmo de registro (n). Como no soy de origen en matemáticas, no puedo relacionarme con él. ¿Alguien puede explicarlo con un poco más de detalle? ¿Tiene que hacer algo con la serie logarítmica?
Aquí está la entrada de wikipedia
Si miras el enfoque iterativo simple. Simplemente está eliminando la mitad de los elementos que se buscarán hasta que encuentre el elemento que necesita.
Aquí está la explicación de cómo se nos ocurre la fórmula.
Digamos que inicialmente tienes N cantidad de elementos y luego lo que haces es ⌊N / 2⌋ como primer intento. Donde N es la suma del límite inferior y el límite superior. El primer valor de tiempo 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 tienes suerte, el elemento que intentas encontrar estará en el medio [ej. Está buscando 18 en la lista {16, 17, 18, 19, 20} luego calcula ⌊ (0 + 4) / 2⌋ = 2 donde 0 es límite inferior (L - índice 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 encontrado. ¡Bingo! Lo encontraste.
Si el caso fuera una matriz diferente {15, 16, 17, 18, 19} pero aún buscabas 18, entonces no tendrías suerte y estarías haciendo primero N / 2 (que es ⌊ (0 + 4) / 2⌋ = 2 y luego darse 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. Por lo tanto, 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 ... hayas terminado de buscar, donde el elemento que estás tratando de encontrar está al final de la lista.
Eso muestra que el peor caso 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, desde el peor caso matemáticamente 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⌋
Aquí una forma más matemática de verlo, aunque no realmente complicado. OMI mucho más clara que las informales:
La pregunta es, ¿cuántas veces puedes dividir N por 2 hasta que tengas 1? Esto es esencialmente decir, haz una búsqueda binaria (la mitad de los elementos) hasta que la encuentres. En una fórmula, esto sería este:
1 = N / 2 x
multiplica 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 tenga todo dividido. Lo que significa que tiene que dividir log N ("hacer el paso de búsqueda binario") hasta que encuentre su elemento.
Como reducimos una lista a la mitad cada vez, solo necesitamos saber en cuántos pasos obtenemos 1 a medida que dividimos una lista por dos. En el cálculo por debajo de 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)
Log2 (n) es la cantidad máxima de búsquedas necesarias para encontrar algo en una búsqueda binaria. El caso promedio involucra búsquedas log2 (n) -1. Aquí hay más información:
No hace la mitad del tiempo de búsqueda, eso no lo haría registrar (n). Lo disminuye logarítmicamente. Piensalo por un momento. Si tenía 128 entradas en una tabla y tenía que buscar linealmente su valor, probablemente le 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 1/2 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 7 es 128). Esto es el poder de la búsqueda binaria
Para búsqueda binaria, T (N) = T (N / 2) + O (1) // la relación de recurrencia
Aplicar el teorema de los másters 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
también, 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))
T (n) = T (n / 2) +1
T (n / 2) = T (n / 4) + 1 + 1
Pon el valor de The (n / 2) en la parte superior de modo 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)
Una búsqueda binaria funciona dividiendo el problema por la mitad repetidamente, algo como esto (detalles omitidos):
Ejemplo que busca 3 en [4,1,3,8,5]
- Ordene su lista de artículos [1,3,4,5,8]
- 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
- Repita el paso 2 con la nueva lista [1, 3], encuentre 3 y pare
Es una búsqueda bi- anual cuando divide el problema en 2.
La búsqueda solo requiere pasos log2 (n) para encontrar el valor correcto.
Recomendaría Introduction to Algorithms si quiere aprender sobre la complejidad algorítmica.
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á el log n .
Esto es solo una jerga matemática formal para poder probar declaraciones, etc. Tiene una explicación muy directa. Cuando n crece muy grande, 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 cual 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 x iteraciones, ¿cuánto tiempo puede el algoritmo de búsqueda binaria en max examinar? La respuesta es 2 ^ x. De esto podemos ver que el reverso es que, en promedio, el algoritmo de búsqueda binaria necesita log2 n iteraciones para una lista de longitud n.
Si el motivo es O (log n) y no O (log2 n), es porque simplemente se vuelve a poner. Usar las grandes constantes de notación O no cuenta.