Con frecuencia esto ocurrirá con tamaños de datos muy pequeños. Muchos de los algoritmos rápidos escalan mucho mejor, pero tienen una sobrecarga mucho más alta que un enfoque más simple e ingenuo. Es bastante común probar el tamaño de los datos y utilizar el enfoque ingenuo si es lo suficientemente pequeño, creando efectivamente un algoritmo híbrido, especialmente si es recursivo.
Además, muchos algoritmos tienen un costo de caso peor que es diferente del caso promedio. la ordenación rápida, por ejemplo, tiene una peor complejidad de n ^ 2. Se toman muchas medidas para evitar este escenario, pero si lo logra, puede hacerlo peor que un algoritmo más lento.
Diferentes algoritmos también pueden escalar en diferentes aspectos del problema. Por ejemplo, una clasificación de radix se escala en función de la longitud de los números que se ordenarán, mientras que una clasificación rápida se calcula en función de cuántos. quicksort es n lg (n), mientras que la clasificación de radix es n * d, donde d es el número de dígitos. cómo se comparan entre sí dependerá de la relación entre d y lg (n), y existen propiedades de los datos que mostrarán que uno supera al otro o viceversa. O con un algoritmo gráfico, un enfoque puede escalar en función del número de aristas y el otro el número de nodos.
A veces, un algoritmo será más rápido para un conjunto de datos en un hardware determinado. Si uno toma más memoria y termina teniendo que usar el disco duro en lugar de puramente ram, se necesitará un gran impacto en el rendimiento que fácilmente puede superar una gran diferencia de O. O un enfoque puede estar vinculado al disco mientras que el otro está vinculado a la CPU, por lo que depende de qué recursos sean más abundantes.
¿En qué condiciones funcionaría un algoritmo lento más rápido que un algoritmo rápido?
Suponiendo que de manera rápida y lenta estás hablando de notación Big-O, un ejemplo fácil es comparar factores constantes.
Ejemplo: una búsqueda binaria en una matriz muy pequeña (digamos 10 elementos) es más lenta que la exploración lineal.
Puede haber muchas condiciones en las que un algoritmo generalmente más lento funciona más rápido que un algoritmo generalmente más rápido. Por ejemplo, la ordenación por inserción es más rápida para entradas pequeñas en comparación con la clasificación rápida. Sin embargo, en términos de tiempo promedio de ejecución, la complejidad del ordenamiento rápido O (nlogn) es mejor que la del tipo de inserción O (n ^ 2). Algo similar sucede también con un conjunto de datos donde la mayoría de los datos están casi ordenados.
En términos generales, ningún algoritmo es el algoritmo más rápido para todos los escenarios posibles y, en su mayoría, existe un algoritmo más lento para el subconjunto del problema que funciona más rápido que el algoritmo supuestamente más rápido.
Los algoritmos no pueden ser inherentemente rápidos o lentos.
Un algoritmo, implementado en software, que se ejecuta en una configuración de hardware en particular, en una entrada en particular, puede ser rápido o lento, porque realmente puede cronometrarlo.
Supongo que podría tener un algoritmo que es teóricamente más rápido (menos instrucciones), pero tiene más errores de caché que otro que debería ser más lento pero tiene una mejor localidad en su acceso a datos.
Además, muchas optimizaciones intercambian una cierta cantidad de configuración por cálculos de consulta más rápidos, como colocar inicialmente puntos de datos en una estructura espacial como un árbol de octree o kd. Por lo tanto, si el tamaño de su conjunto de datos es demasiado pequeño, el cálculo previo inicial podría no valer la pena.
Los algoritmos se clasifican como lentos o rápidos en función de su comportamiento asintótico, por lo que en casos de pequeños problemas, un algoritmo lento puede ser más rápido que uno rápido.
More Interesting
¿Cómo debería abordar el problema de segmentar el césped de una imagen?
Cómo derivar la propagación hacia atrás desde la segunda capa de convolución
¿A qué tipo de problemas del mundo real se aplica el aprendizaje no supervisado?
En clasificación, ¿cómo manejas un conjunto de entrenamiento desequilibrado?
