Existen muchos algoritmos que solo funcionan prácticamente en tamaños de entrada pequeños.
Cuando hablamos del tiempo de ejecución de un algoritmo (o complejidad de tiempo ), generalmente expresamos esto en notación “Big O”.
Un ejemplo simple de esto es la diferencia en tiempo de ejecución entre Mergesort y el tipo de inserción. Mergesort utiliza un método de división y conquista, por lo que duplicar el conjunto de entrada aumenta su tiempo de ejecución linealmente (es un poco más complejo que esto, pero tenga paciencia conmigo). Por lo tanto, Mergesort es O (n * log n). La ordenación por inserción no es un algoritmo tan inteligente y compara cada elemento con, en el peor de los casos, todos los demás elementos del conjunto de entrada. Por lo tanto, es O (n ^ 2).
- ¿Qué matemática puede o no puede hacer una computadora?
- Cómo imprimir el conjunto de potencia de un conjunto finito de enteros en Java usando recursividad
- Cómo implementar la diferenciación automática en C ++ desde cero
- ¿Cuáles son algunas aplicaciones del mundo real de la teoría de la información cuántica?
- ¿Qué son los métodos flexibles de aprendizaje estadístico?
Entonces, para responder a su pregunta, supongamos que tenemos un conjunto de 10 elementos que queremos clasificar. Ambos algoritmos funcionarán esencialmente en la misma cantidad de tiempo, porque el tamaño de la muestra es muy pequeño. Sin embargo, a medida que aumentamos nuestro conjunto de entrada, esto ya no es cierto. La clasificación de mil millones de elementos podría llevar horas y horas con la ordenación por inserción, pero tal vez minutos con la ordenación por fusión, como ejemplo.
Entonces sí. Hay algoritmos que son increíblemente poco prácticos a gran escala.
Q adicionales:
¿Por qué mergesort en 10 elementos y mergesort en 11 elementos se tratan como el mismo algoritmo?
Porque simples son el mismo algoritmo. La entrada de mergesort es un conjunto arbitrariamente grande. Las operaciones realizadas en ese conjunto son las mismas, es decir, independientemente del tamaño de entrada. Un algoritmo es solo un conjunto de tareas ordenadas y específicas. En aras de una implementación sensata, la mayoría de los algoritmos son independientes del tamaño.
¿Por qué construimos algoritmos para que funcionen en diferentes tamaños de entrada?
Principalmente por razones prácticas. La ordenación por inserción es un algoritmo mucho más simple, por ejemplo, y no lleva mucho tiempo implementarlo.
Este argumento es un poco discutible porque muchos algoritmos están estandarizados en bibliotecas, pero el principal aún se mantiene. Usted diseña algoritmos a la escala para la que se usan. No es necesario invertir un tiempo valioso en la creación de un algoritmo escalable si solo se usa con conjuntos pequeños.
¿Hay alguna razón teórica para esto (por ejemplo, un teorema que establece que cada algoritmo se puede extender de manera significativa para un tamaño de entrada arbitrario) o existen algoritmos que funcionan solo en una longitud de entrada fija y no se pueden extender fácilmente?
No tengo una gran respuesta a esta pregunta, pero me interesaría un poco en el análisis de algoritmos y la complejidad del tiempo si está interesado. Hay una diferencia entre el diseño de algoritmos teóricos y la aplicación práctica de algoritmos. Caso en cuestión: Bogosort, que tiene el peor tiempo de ejecución de O ((n + 1)!) Podría usarse para clasificar 2 elementos o 2 mil millones de elementos. Algorítmicamente, no hay razón para que esto no funcione. Sin embargo, O ((n + 1)!) De 2 mil millones probablemente correría hasta literalmente el final del universo sin completarse. Ahí vas. Teóricamente, podría funcionar. Prácticamente, no es una oportunidad.
