La línea 1 se ejecuta n veces.
La línea 2 se ejecuta n veces.
Las líneas 3 se ejecutan una vez más que su iteración anterior. En otras palabras, se ejecuta 1 vez cuando j = i, luego se ejecuta dos veces cuando j = 2 hasta j = n. Entonces tienes 1 + 2 + 3 + .. + (n – 2) + (n – 1) + n. Esta es la suma de los primeros n enteros que es igual a (n * (n + 1)) / 2 = (n ^ 2 + n) / 2. Descartando el coeficiente y manteniendo solo el término dominante se obtiene n ^ 2.
- En términos simples, ¿qué quieres decir con enmarcar bits?
- ¿Cómo funciona la calculadora HSBC?
- ¿Puede una máquina tener verdadera inteligencia artificial sin estar basada en matemáticas superiores?
- ¿Se pueden convertir las máquinas de Turing en un DFA?
- Dado un número X, encuentre el siguiente número con el mismo número de 1 bits en su representación binaria. Para la entrada x = 12, ¿la salida sería 17?
Dado que los 3 bucles for están anidados, debe multiplicar cada uno de los tiempos de ejecución juntos, que es n * n * n ^ 2 = n ^ 4. Sin embargo, esto no significa que el tiempo de ejecución sea n ^ 4, ya que debe ver cuál es el tiempo de ejecución para los otros 2 bucles anidados.
Las líneas 5 se ejecutan n ^ 2 veces.
Las líneas 6 se ejecutan de la misma manera que las líneas 3, pero se ejecuta desde 0 .. n ^ 2. Entonces la fórmula es (n ^ 2 * (n ^ 2 + 1)) / 2 = (n ^ 4 + n ^ 2) / 2. Soltando constantes y manteniendo solo el término dominante obtienes n ^ 4.
Dado que tiene dos grupos de bucles anidados, debe agregar los tiempos de ejecución juntos, por lo que ahora tiene n ^ 4 + n ^ 4 = 2n ^ 4. Al soltar el coeficiente, obtienes n ^ 4. Ese es el razonamiento.
