Si desea buscar una palabra a través del diccionario, debe encontrar la primera letra de la palabra. El diccionario abarca desde AZ, 26 letras. Un enfoque iterativo sería mirar cada letra e ir a la siguiente si aún no la encuentra, que son 26 letras.
Un enfoque de búsqueda binaria dividiría el diccionario por dos y verificaría qué lado es el derecho. Entonces, si desea encontrar la letra ‘C’, divida el diccionario en ‘M’. Está a la izquierda, porque C viene antes que M.
¿Cual es la diferencia? Bueno, un enfoque iterativo / ingenuo es [matemático] O (N) [/ matemático] mientras que un enfoque de búsqueda binaria es [matemático] O (log_2 N) [/ matemático] (¿por qué es [matemático] log_2 [/ matemático] y no [math] log_ {10} [/ math]?)
- ¿Por qué los conjuntos en Python tienen una complejidad algorítmica de O (1)?
- ¿Cómo resolver la pregunta 1 de ZIO2015? ¿Es un enfoque de programación dinámica?
- ¿Qué tecnologías y algoritmos se usan comúnmente para la resolución de entidades basadas en una intersección de algunos atributos?
- ¿Cuál es la intuición de los algoritmos de Prim y el algoritmo de Kruskal?
- ¿Codeforces tiene un problema de ética?
Un enfoque de búsqueda binaria es un algoritmo rápido en comparación con un enfoque iterativo (porque rápido es relativo) porque divide el espacio de búsqueda por un factor de 2 cada vez que realiza una operación.
Si tuviera un espacio de búsqueda de un billón de letras, un enfoque iterativo necesitaría, en el peor de los casos, un billón de operaciones. Un enfoque de búsqueda binaria necesitaría, en el peor de los casos, 20 operaciones.
