Seguro. Ese es el objetivo de tratar de optimizar las búsquedas mediante la clasificación previa, la indexación, la agrupación, etc.
Cuando quieres buscar algo en el diccionario, ¿necesitas log (n)?
Por supuesto no. Puede hacer una primera suposición basada en la proporcionalidad a la ubicación en el alfabeto, y luego hacer suposiciones más precisas desde allí.
Dado que un diccionario de papel está organizado por páginas, siempre puede saltar al menos una página completa a la vez, simplemente escaneando la última entrada en cada página.
Nunca tiene que escanear cada entrada individual.
Si desea comprender esto de una manera más general, busque B + Trees, la estructura de datos de almacenamiento más eficiente jamás diseñada. Correctamente equilibrado, requiere muy pocas búsquedas, independientemente de los datos del peor de los casos.
B + árbol
¿Hay algún algoritmo que sea más rápido que log (n)?
Related Content
¿Cuál es la mejor manera de extrapolar una señal dispersa que proviene de un filtro de Kalman?
¿Cómo resolver el problema de los genéricos?
¿Cómo creo más interés en la programación y soy un buen programador en algoritmos?
Seguro. Cualquier algoritmo que pueda calcular el resultado en tiempo constante es más rápido que log (n). Por ejemplo, el algoritmo ingenuo para calcular la función f (n) = 0.
Para algo un poco menos trivial, mientras que encontrar un elemento arbitrario en una matriz ordenada de n elementos requiere tiempo O (log (n)) (usando búsqueda binaria), y no hay una manera más rápida de hacerlo, encontrando el mínimo / máximo / mediano del mismo arreglo ordenado requiere solo O (1) tiempo, significativamente más rápido.
La búsqueda de interpolación puede ser [matemática] O (\ log {\ log {n}}) [/ matemática] bajo ciertas condiciones. La búsqueda de la tabla hash es [matemática] O (1) [/ matemática] en el límite de “no demasiado lleno”.
Sí, por ejemplo, encontrar el primer elemento de una lista es O (1).
¡No se ralentiza en absoluto para listas más largas!
Las operaciones en una unión de datos de búsqueda de unión implementada correctamente es O (Ai (n)), donde Ai es la función inversa de Ackerman. Crece sin límite, pero mucho más lento que log (n).
Aquí hay uno:
Paso 1. x = 2
Cualquier serie de pasos dados para lograr un objetivo, es un algoritmo.
More Interesting
¿Cuál es el uso práctico de los árboles de búsqueda binarios?
¿Cuál es la diferencia entre la recursión normal y la recursiva de la cola con ejemplos?
¿Cuál es la explicación de este código?
¿Por qué los conjuntos en Python tienen una complejidad algorítmica de O (1)?
¿Por qué las computadoras se crean de tal manera que entiendan 0s y 1s?
¿Cómo funciona la ordenación por fusión en C ++?
¿Cuál es el algoritmo para el deporte de fantasía diario?
¿Cuál es el curso / certificación mejor pagado disponible para estructuras de datos y algoritmo?
¿Qué es una explicación intuitiva de inserción en un árbol AVL?
