El código real a menudo puede usar algoritmos exponenciales, que crecen más rápido que cualquier algoritmo polinomial.
La complejidad computacional es un elemento importante de la elección del algoritmo, pero no es el único. El tamaño del conjunto de datos también es crucial. La notación asintótica le dice qué tan lento puede llegar a ser el problema, pero no todos los problemas del mundo real realmente crecen sin límites. Para valores pequeños de N, el factor constante puede dominar.
E incluso cuando es más lento, el algoritmo exponencial se puede elegir por razones de corrección y simplicidad. El objetivo no es obtener el código más rápido; es para obtener el código lo suficientemente rápido. Si está hablando de algo que sucede entre las interacciones del usuario, no importa si toma 10 microsegundos o 1 microsegundo. Ambos son imperceptibles para el usuario, a pesar de ser un orden de diferencia de magnitud. El algoritmo exponencial puede ser correcto y sencillo de codificar; no hay razón para soportar algo más complejo si no es necesario.
- ¿Debería un ingeniero que no sea CS aprender programación, algoritmos y estructuras de datos?
- Cómo abordar el problema 'Mapa intergaláctico' (IM) en SPOJ usando Max Flow
- ¿Qué esfuerzos hará para crear un gráfico de la estructura de datos básicos, que también puede ser entendido por una persona no técnica?
- ¿Qué tipo de estrategias y algoritmos tenemos en el comercio cuantitativo?
- ¿Cuál es el algoritmo de compresión de texto más utilizado en la industria?
En el sistema con el que trabajo ahora, hay un problema de optimización en el núcleo. Para valores pequeños de N, solucionamos el problema por completo. Para la mayoría de los problemas, a menudo tenemos N en el rango de 2 o 3, y no hay razón para no hacerlo de la manera “difícil”. El código es simple y directo, y se ejecuta al menos igual de rápido. Tenemos una aproximación para cuando N crece, y ese código es una molestia, porque tiene que estar lleno de hacks para casos patológicos. (Tener que mantener ambos conjuntos de código es otra molestia, y creo que nos hemos librado del planificador exacto, lo cual es una lástima).