¿Qué significa decir "Asintóticamente más eficiente"?

¿Qué significa cuando decimos que un algoritmo es asintóticamente más eficiente que ?$X$$Y$

• $X$ será una mejor opción para todas las entradas.
• $X$ será una mejor opción para todas las entradas, excepto las entradas pequeñas.
• $X$ será una mejor opción para todas las entradas, excepto las entradas grandes.
• $Y$ será una mejor opción para entradas pequeñas.

El enlace para esta pregunta está aquí.

http://quiz.geeksforgeeks.org/algorithms-analysis-of-algorithms-question-16/

Pensé que un algoritmo más asintóticamente eficiente debería funcionar para todas las entradas, pero no entiendo la razón detrás de "Funciona para todas las entradas excepto las pequeñas".

En primer lugar, ambos algoritmos "funcionan" para todas las entradas. La pregunta es sobre el rendimiento.

Las respuestas a esa pregunta son un poco malas. Una forma de decir que un algoritmo es asintóticamente más eficiente que otro es si hay un tamaño de entrada (específico del problema) tal que para cualquier tamaño de entrada más grande, el algoritmo más eficiente tomará menos "pasos computacionales", generalmente por alguna medida abstracta, por ejemplo Número de comparaciones.

La idea de las respuestas es que un algoritmo asintóticamente más eficiente aún puede requerir más pasos antes de ese tamaño de entrada. Se puede darse el caso de que el algoritmo asintóticamente más eficiente requiere menos pasos para todas las entradas, pero no tiene por qué ser el caso y en la práctica por lo general no lo es. Por lo tanto, una mejor redacción de la respuesta "correcta" sería " será una mejor opción para todas las entradas, excepto las entradas posiblemente pequeñas".$X$

Sin embargo, la redacción aún no es tan buena. En primer lugar, hay muchos más factores para decidir qué algoritmo es una "mejor opción", pero les daré que la intención es lo suficientemente clara en este caso. El verdadero problema es "pequeño" y "grande". Uno de mis trabajos favoritos es El algoritmo más rápido y más corto para todos los problemas bien definidos . Este documento describe un algoritmo que, dada cualquier especificación de una función, y una prueba de que se puede calcular en tiempo polinomial calculará esa función en una complejidad de tiempo óptima dentro de un factor de más un término aditivo. Por ejemplo,$5$ , produciría un algoritmo de clasificación que era O ( n lg n ) . De hecho, produciría un algoritmo que era 5 c n lg n + o ( n lg n ) donde c era el factor constante delalgoritmoasintóticamente^*óptimo. Esto es increíble. Solo hay un problema: eltérmino constante , oculto en el o ( n lg n $O(n^2)$$O(n\lg n)$$5cn\lg n + o(n\lg n)$$c$$o(n\lg n)$en este ejemplo, hace que el algoritmo sea casi completamente inviable para prácticamente cualquier problema real. ¿Qué quiero decir con "completamente inviable"? Quiero decir que la muerte por calor del universo sucederá muchas veces antes de que se complete ese algoritmo. Sin embargo, para entradas adecuadamente "grandes" será más rápido que el tipo burbuja. Mi punto es que es casi seguro que no sea físicamente posible escribir de ninguna manera una entrada "adecuadamente grande", y mucho menos calcularla.

En cualquier caso, la forma en que diría la respuesta correcta sería: " requiere menos pasos que Y en entradas suficientemente grandes". Esto todavía es un poco vago, ya que existen múltiples nociones de "paso" que podrían aplicarse y un algoritmo podría ser asintóticamente más eficiente por una métrica y menos eficiente por otra. Esta redacción evita el juicio de valor de "mejor opción"; Hay muchas razones para elegir algoritmos asintóticamente menos eficientes o incluso algoritmos menos eficientes cuando se especifican factores / términos constantes, como la eficiencia de la caché o la simplicidad de implementación.$X$$Y$

^* Aquí hay una sutileza. El algoritmo asintóticamente óptimo puede tener un factor constante peor, , que un algoritmo asintóticamente no óptimo. Creo que tendrá el mejor valor de c para cualquier algoritmo asintóticamente óptimo, pero es concebible que para obtener una ligera ganancia en eficiencia asintótica, se agregue una complejidad masiva que aumente significativamente el factor constante.$c$$c$

Lo que la gente suele decir cuando dice algo como esto es:

$T_A$$T_B$$A$$B$$T_A \in o(T_B)$

$X$

En particular, ninguna de las declaraciones que propone sigue, a pesar de que las personas a menudo sugieren que la segunda lo hizo.

Lamentablemente, la comunidad más amplia de personas que trabajan con algoritmos adopta una terminología que raya en vacuo en aras de la simplicidad. (¡Hacer declaraciones precisas y útiles sobre algoritmos es difícil!)

Puede estar interesado en nuestras preguntas de referencia .

Se dice que un algoritmo X es asintóticamente mejor que Y si X toma un tiempo menor que y para todos los tamaños de entrada n mayores que un valor n0 donde n0> 0.

$T_A(n) = n+1$$T_B(n) = n$

Te recomiendo que aprendas ciencias de la computación a partir de recursos de CS, no de programadores que hayan leído sobre Wikipedia una vez. (Sí, eso es duro, pero he visto demasiadas falsedades propagadas en círculos de programadores, incluso en SO).

"Asintóticamente más eficiente" significa "más eficiente para todos los problemas por encima de cierto tamaño". No dice cuál es el "cierto tamaño", y no dice qué sucede antes de ese "cierto tamaño".

Por lo tanto, todas las respuestas, excepto la segunda, son claramente incorrectas, porque "Asintóticamente más eficiente" no dice nada sobre los tamaños de entrada pequeños. Pero el segundo también es problemático.

$10^{30}$$10^{30}$$10^{40}$

$10^{15}$