Sea un poco específico al hacer preguntas como para qué caso, desea conocer el mejor algoritmo de búsqueda. No voy a entrar en la implementación de ningún algoritmo; simplemente googlear sería suficiente para eso.
Cada algoritmo de búsqueda tiene sus propias ventajas y desventajas. Dependiendo de sus recursos y requisitos, se selecciona el más adecuado. Sin embargo, la mayoría de las veces, el mejor algoritmo es el más rápido, pero a veces tenemos poco espacio.
- Teniendo en cuenta un caso en el que debe buscar un elemento en una lista, dos posibles algoritmos de búsqueda: búsqueda lineal y binaria .
Búsqueda lineal:
Recorra la lista y verifique si el elemento actual coincide con nuestra clave o no. Complejidad de tiempo: O (n) – lineal- ¿Las compañías aéreas han mejorado la eficiencia de sus algoritmos de sobreventa?
- Yoshua Bengio: ¿Puede el aprendizaje profundo encontrar un nuevo algoritmo de clasificación?
- ¿Cuántos números debajo de [matemática] 10 ^ n [/ matemática] hay cuyos dígitos suman [matemática] [/ matemática]?
- ¿Cómo funcionan los algoritmos genéticos en la programación?
- ¿Cuál es el libro más legible y efectivo para aprender introducción a los algoritmos informáticos?
Búsqueda binaria :
El algoritmo de búsqueda más elegante pero requiere una lista ordenada.
Complejidad del tiempo: O (logn)Un enfoque diferente:
En un caso de rango restringido y recuento de números, podríamos usar conceptos similares como el hash y el conteo para buscar en tiempo constante (O (1)).
/ * Necesitamos buscar un elemento num en una lista * /
int list [] = {5,15,78,10,178,44}; // nuestra lista
cheque booleano [100] = {false}; // comprueba la matriz para la utilidad de búsqueda
check [5] = check [15] = check [78] = check [10] = check [44] = verdadero;
int num = 10; // número que necesitamos buscar en la lista
if (marque [num] == verdadero) {
// elemento encontrado
} más {
// elemento no encontrado
}
- Algoritmos de búsqueda de cadenas
Los más famosos son: KMP (Knuth Morris Pratt), Rabin Karp y Autómata de estado finito. Pocas estructuras de datos como Tries también se utilizan.
Además de estos algoritmos de búsqueda generales, hay varias estructuras de datos especializadas utilizadas para fines de búsqueda, como árboles de segmentos , árboles de búsqueda binaria , árboles kd , etc., cada uno con su propio propósito, como la búsqueda de rango, etc.
TL; DR
En general, se dice que la búsqueda binaria es el mejor algoritmo de búsqueda a menos que se indique lo contrario.
Bienvenido al vasto mundo de la programación 😉
