Estimador de eficiencia
Calcula la complejidad temporal de funciones y algoritmos.
¡Copia este prompt en nuestra Consola de desarrollador para probarlo tú mismo!
Contenido | |
---|---|
System | Tu tarea es analizar la función o algoritmo proporcionado y calcular su complejidad temporal utilizando la notación Big O. Explica tu razonamiento paso a paso, describiendo cómo llegaste a la complejidad temporal final. Considera el peor de los casos al determinar la complejidad temporal. Si la función o algoritmo contiene múltiples pasos o bucles anidados, proporciona la complejidad temporal para cada paso y luego da la complejidad temporal general para toda la función o algoritmo. Asume que cualquier función u operación incorporada utilizada tiene una complejidad temporal de O(1) a menos que se especifique lo contrario. |
User | def example_function(n): for i in range(n): print(i) for j in range(n): for k in range(n): print(j, k) |
Ejemplo de salida
Para analizar la complejidad temporal de la función dada
example_function(n)
, la dividiremos en pasos y consideraremos el peor de los casos.Paso 1: Analizando el primer bucle
for i in range(n): print(i)
Este bucle itera
n
veces y realiza una operación de tiempo constante (print(i)
) en cada iteración. Por lo tanto, la complejidad temporal de este paso es O(n).Paso 2: Analizando los bucles anidados
for j in range(n): for k in range(n): print(j, k)
El bucle externo itera
n
veces, y para cada iteración, el bucle interno también iteran
veces. En cada iteración del bucle interno, se realiza una operación de tiempo constante (print(j, k)
). Por lo tanto, la complejidad temporal de los bucles anidados es O(n * n) = O(n^2).Paso 3: Combinando las complejidades temporales
La funciónexample_function(n)
consta de dos pasos: el primer bucle y los bucles anidados. La complejidad temporal general es la suma de las complejidades temporales de cada paso.Complejidad temporal del primer bucle: O(n)
Complejidad temporal de los bucles anidados: O(n^2)Para determinar la complejidad temporal general, consideramos el término dominante, que es el término con el orden de crecimiento más alto. En este caso, O(n^2) domina a O(n).
Por lo tanto, la complejidad temporal general de la función
example_function(n)
es O(n^2).En el peor de los casos, cuando
n
es grande, los bucles anidados dominarán el tiempo de ejecución, y la función tendrá una complejidad temporal cuadrática.