¿Exactamente cuánto más rápido es la búsqueda binaria?
En esta página, compararás el tiempo que se requiere para realizar una búsqueda binaria y una búsqueda lineal.
La cantidad actual de tiempo físico que se necesita para resolver un problema depende no solo de tu algoritmo, sino también de la velocidad de tu ordenador y de qué otros programas tienes en ejecución, etc. Por lo tanto, los informáticos que quieren medir la velocidad de un algoritmo lo hacen en términos del número de pasos. Por ejemplo, lo qué realmente queremos saber sobre la eficiencia del algoritmo de búsqueda lineal es cúantas veces el elemento actual es comparado al valor (es decir, cuántas veces 
es llamado).
-
AAP-2.P.3
Añade otra columna a tu tabla. Asumiendo que "zumo" es la última palabra en cada lista de palabras, ¿cuántas comparaciones son hechas por el algoritmo de búsqueda lineal para cada lista?
| Longitud de la lista |
Tiempo de la búsqueda lineal |
Pasos de la búsqueda lineal |
| 1000 |
|
|
| 10,000 |
|
|
| 100,000 |
|
|
¿Cómo describirías lo que sucede con el número de pasos a medida que la lista de entradas se hace más grande? Escribe tu hipótesis sobre este patrón.- ¿Lo que sucede con los pasos coincide con lo que sucede con el tiempo? Es decir, ¿puedes contar los pasos como una medida de tiempo?
:
Eficiencia
AAP-4.A.3
La relación entre el tamaño de la entrada y el número de pasos requeridos para resolver un problema es la eficiencia (efficiency) del algoritmo utilizado para resolver el problema.
AAP-4.A.4, AAP-4.A.5
Contando el número de pasos, como lo acabas de hacer, es informal, pero es una buena forma de determinar la eficiencia de un algoritmo. La medición formal de un algoritmo requiere de una prueba matemática.
En este curso, la mayoría de las veces estás trabajando con problemas pequeños, por lo que no importa lo eficiente que sea el algoritmo. Pero en el mundo real, los programadores se ocupan de listas de miles de millones de elementos, por lo que la eficiencia de un algoritmo puede marcar una gran diferencia.
-
AAP-2.P part a
AAP-2.P.3
Ahora, prueba cuánto tiempo le toma a la búsqueda binaria encontrar la palabra "zumo" en las listas clasificadas, y determina cuántas comparaciones por el algoritmo si "zumo" es la última palabra en cada lista.
| Longitud de la lista |
Tiempo de la búsqueda lineal |
Pasos de la búsqueda lineal |
| 1000 |
|
|
| 10,000 |
|
|
| 100,000 |
|
|
- Describe lo que sucede con el tiempo y el número de pasos a medida que la lista de entradas se hace más grande. Escribe tu hipótesis.
-
AAP-2.P.3, AAP-4.A.6
Mira de nuevo tus tablas de algoritmos para la búsqueda lineal y la búsqueda binaria, y compara los dos algoritmos de búsqueda:
- ¿Cúal tiene más bloques en su código?
- ¿Cuál se ejecuta más rápido para grandes entradas?
- ¿Qué algoritmo es más eficiente?
-
AAP-2.P part b
¿Cuáles son los dos requerimientos para utilizar la búsqueda binaria?
incluido en tu proyecto y mira dentro de él. Compáralo con el algoritmo que usaste para contar el número de palabras de cinco o siete letras. Este bloque hace el mismo cálculo que el bloque de búsqueda binaria, pero utiliza el algoritmo lineal.
para probar cuánto tiempo le toma a la