Muy usualmente, pero no siempre. El análisis asintótico considera el peor de los casos y barre las constantes aditivas y multiplicativas debajo de la alfombra. Los algoritmos con un mejor tiempo de ejecución asintótico funcionarán mejor en entradas más grandes que un cierto tamaño, pero ese tamaño puede ser enorme, o las constantes ocultas en la notación big-O pueden ser absolutamente masivas.
Un ejemplo muy práctico: cuando se ordenan listas pequeñas (quizás unos cientos de elementos o más cortas), se sabe que ciertos algoritmos O (n ^ 2) se ejecutan más rápido que los hábiles algoritmos O (n log n) que son mucho mejores asintóticamente. (En estos tamaños de entrada más pequeños, las constantes realmente importan y la sobrecarga de recursión excesiva comienza a sumarse …) Muchos algoritmos de clasificación altamente optimizados para el rendimiento realmente cambian a la clasificación de burbujas (o algo así) después de haber dividido la entrada en subproblemas lo suficientemente pequeños.
También considere que un algoritmo muy inteligente con una complejidad asintótica asesina podría ser muy difícil de implementar. Este es el caso con varias estructuras de datos similares a las del montón más novedosas, como el montón de Fibonacci. (Consulte también las colas Brodal: se obtienen operaciones de almacenamiento dinámico O (1), pero se dice que la implementación es tan desagradable que incluso el inventor piensa que “no son aplicables en la práctica”). Este podría ser el caso para algunos modernos algoritmos de tabla hash también.
- ¿Cuáles son los algoritmos necesarios para resolver div2 500 y div2 1000 fácilmente en topcoder?
- ¿Cuál es la relación entre el índice de una matriz y el tamaño de una matriz?
- ¿Cuál es la diferencia principal entre algoritmo y pseudocódigo?
- ¿Cuáles podrían ser los buenos proyectos basados en algoritmos?
- Si clasifica todos los pesos de una red neuronal entrenada en orden ascendente, ¿cómo se vería la curva de los datos ordenados?
Y, en ocasiones, el tiempo de ejecución promedio puede ser una consideración más importante. Esto no es muy común, pero especialmente cuando eliges entre algoritmos que usan algún tipo de heurística, incluso si funcionan de manera idéntica en el peor de los casos, puede suceder que uno de ellos no se encuentre con el peor de los casos con tanta frecuencia. Creo que el algoritmo simplex para programación lineal es un buen ejemplo aquí: su tiempo de ejecución promedio es (algo inexplicablemente) bueno, lo que lo convierte en una opción popular en la práctica, pero su peor desempeño aún es bastante terrible.
Gracias por el A2A.
