En este artículo, la atención se centra en aprender algunas reglas que pueden ayudar a determinar el tiempo de ejecución de un algoritmo.
El análisis asintótico se refiere a calcular el tiempo de ejecución de cualquier operación en unidades matemáticas de cálculo. En el análisis asintótico, se evalúa el rendimiento de un algoritmo en términos de tamaño de entrada (no medimos el tiempo de ejecución real). También se calcula cómo el tiempo (o el espacio) tomado por un algoritmo aumenta con el tamaño de entrada.
(g(n)) = {f(n) tal que g(n) es una curva que se aproxima a f(n) a valores más altos del tamaño de entrada, n}
Esta curva se llama curva asintótica y el análisis del algoritmo para tal curva se llama análisis asintótico .
Bucles : el tiempo de ejecución de un bucle es, como máximo, el tiempo de ejecución de las declaraciones dentro del bucle, incluidas las pruebas) multiplicado por el número de iteraciones.
A continuación se muestra el programa de Python que demuestra el concepto anterior:
Python3
# Python program to implement
# the above concept
# execute n times for in
# range(0.00);
for i in range(0, n):
print ('Current Number:', i, sep = "")
#constant time Total time a constant cx n = cn = O(n).
Bucles anidados : Analice de adentro hacia afuera. El tiempo de ejecución total es el producto de los tamaños de todos los bucles.
A continuación se muestra un programa de Python que demuestra el concepto anterior:
Python3
# Python program to implement
# the above concept
# outer loop executed n times
for i in range(0, n):
# inner loop executes n times
for j in range(0, n):
print("i value % d and j value % d" % (i, j))
# constant time Total time = C x n x n = cn^2 =0(n²).
Sentencias consecutivas : agregue la complejidad temporal de cada sentencia.
A continuación se muestra un programa de Python que demuestra el concepto anterior:
Python3
# Python program that implements
# the above concept
n = 100
# executes n times
for i in range (0, n):
print (Current Number: i, sep = "")
# outer loop executed n times
for i in range (0, n):
# inner loop executes n times
for j in range(0, n):
print(" i value % d and j value % d"%(i, j))
X
Total time = co + c1n + c2n^2 = 0(n^2).
Declaraciones if-then-else : tiempo de ejecución en el peor de los casos: la prueba, más la parte entonces de la parte else, la que sea mayor.
A continuación se muestra un programa de Python que demuestra el concepto anterior:
Python3
# Python program that implements
# the above concept
if n == I:
print ("Incorrect Value")
print (n)
else:
for i in range(0, n):
# constant time
print (CurrNumber:, i, sep = "")
Total time = co + c1*n = 0(n).