Aquí hay un ejemplo sobre cómo analizar la complejidad del tiempo de los diferentes algoritmos de multiplicación de mi libro de texto:
Si hacemos multiplicación por suma repetida:
4 * 7 = 7 + 7 + 7 + 7
La complejidad del tiempo sería O (n * 10 ^ n), donde n es el dígito.
No me siento bien al analizar la complejidad del tiempo cuando n es un dígito. ¿Podría alguien explicarme por qué es O (n * 10 ^ n)?
Respuestas
0 para la respuesta № 1Un número norte tiene O(Iniciar sesión norte) dígitos, donde log denota el logaritmo decimal. La suma de norte consigo mismo por lo tanto requiere O(Iniciar sesión norte) pasos, y haciendo eso METRO los tiempos requieren O(METRO Iniciar sesión norte) pasos. por METRO en O(norte) usted obtiene O(norte Iniciar sesión norte) pasos. Esta estimación se basa en los números. Si quieres el numero de digitos norte como base debes sustituir norte con 10 ^norte, lo que da O(norte 10 ^norte)