Comparación de la complejidad temporal de dos algoritmos (desigualdad)

La pregunta sugiere que dos algoritmos gastan T A ( norte ) = 0.0001 norte 2 , y T B ( norte ) = 50 norte , microsegundos respectivamente, para un tamaño de problema de norte . La pregunta es, ¿a qué tamaño de entrada Algorithm A ser mejor que B . ¿Cómo encuentro esto?

Encontré una pregunta similar con una solución que no entiendo completamente. Los tiempos de ejecución de los algoritmos de una pregunta similar son T A = 0.1 norte 2 registro 2 ⁡ norte y T B = 2.5 norte 2

Se resuelve de la siguiente manera:

2.5 norte 2 < 0.1 norte 2 registro 2 ⁡ norte
2.5 < 0.1 registro 2 ⁡ norte
25 < registro 2 ⁡ norte
2 25 < norte

Por lo tanto, Algoritmo B es mejor cuando norte es mayor que 2 25

Entiendo el concepto de tener que usar la desigualdad para probar que 0.0001 norte 2 < 50 norte , sin embargo, me cuesta entender qué se está haciendo en la solución del ejemplo y cómo aplicarlo a la pregunta...

Creo que su pregunta es un poco incorrecta. Esto se debe a norte 3 / 2 no puede ser acotado por una cantidad constante cuando norte → ∞ o dicho de otra manera cuando norte es lo suficientemente grande, no puede ser acotado por ninguna constante.
@Kumar Supongo que es posible, aunque creo que es más probable que lo haya expresado de manera diferente a como lo tengo, así que lo reiteraré textualmente y, con suerte, eso podría ayudar a aclarar las cosas. "Los algoritmos A y B gastan exactamente TA(n) = 0.0001n^2 y TB(n) = 50√𝑛 microsegundos, respectivamente, para un problema de tamaño n. Determine el tamaño del problema n0 para el cual el "mejor" algoritmo comienza a superar al otro suponiendo que n0 > 0".
La última declaración de su comentario debe ser su pregunta real en lugar de un comentario. y como sea, lo dicho se da como respuesta @DavideFiocco.

Respuestas (1)

Suponga que los dos algoritmos resuelven el mismo problema. En ese caso se puede decir que el algoritmo A es mejor que el B si T A < T B , porque el primero corre en un tiempo más corto.

¿Para qué valores (positivos) de n hace eso T A < T B ¿Se mantiene la desigualdad? Sustituyendo las expresiones de T A y T B usted obtiene

0.0001 norte 2 < 50 norte .

Puede aprender cómo se puede resolver una desigualdad de este tipo con lápiz y papel, por ejemplo, aquí , o resolverla gráfica y algebraicamente usando un motor para matemáticas simbólicas como Wolfram Alpha. Si haces eso, verás que T A es más pequeña que T B solo si n es menor que algún valor de umbral. Más allá de ese umbral, el algoritmo B "se pone mejor que A " porque una función de raíz cuadrada (como T B ( norte ) ) aumenta más lentamente que uno cuadrático (como T A ( norte ) ) a medida que n aumenta.

@Varehen Considere eliminar la misma pregunta publicada en StackOverflow stackoverflow.com/questions/58019830/… :)
Comparación de la complejidad temporal de dos algoritmos (desigualdad)
RespuestasAquíPolítica de privacidad1y, 1v