Complejidad algorítmica
¿Ya tomaste el Curso de Pensamiento Computacional?
Introducción a la complejidad algorítmica
Abstracción
Notación asintótica
Clases de complejidad algorítmica
Algoritmos de búsqueda y ordenación
Búsqueda lineal
Búsqueda binaria
Ordenamiento de burbuja
Ordenamiento por inserción
Ordenamiento por mezcla
Ambientes virtuales
Ambientes virtuales
Graficado
¿Por qué graficar?
Graficado simple
Algoritmos de optimización
Introducción a la optimización
El problema del morral
Conclusiones
No tienes acceso a esta clase
¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera
Aportes 116
Preguntas 21
Interesante tema. En algunas entrevistas y pruebas tecnicas lo preguntan. Ademas que esto se debe pensar al implementar/mejorar cualquier algoritmo.
Comparto mi “conteo de operaciones” para el calculo de la raiz cuadrada de 2 usando los algoritmos vistos en el curso “Curso de Introducción al Pensamiento Computacional con Python”
def raizbruta(numero, epsilon = .0001):
"""
Calcula la raiz cuadrada con un error de epsilon recorriendo los números flotantes entre
0 y numero con un paso de epsilon
numero float >0 al cual se calcula la raíz
epsilon float >0 tolerancia del error
"""
assert type(numero) == float, f'argumento número debe tener formato float'
assert numero >0, f'argumento número debe ser positivo'
assert type(epsilon) == float, f'argumento epsilon debe tener formato float'
assert epsilon >0, f'argumento epsilon debe ser positivo'
prueba = epsilon
conteo = 1
while numero-prueba**2 > epsilon:
prueba += epsilon
conteo += 4
"""
1 elevar al cuadrado
1 restar numero-prueba**2
1 evaluar desigualdad
1 sumar epsilon
4 total sin contar asignaciones
"""
print(f'Con una tolerancia de {epsilon} se usaron {conteo} cálculos para raizbruta')
return prueba
def raizbiseccion(numero, epsilon = .0001):
"""
Calcula la raiz con la busqueda por bisección para un error de epsilon.
numero float >0 del cual queremos la raiz
epsilon float >0 es el error o tolerancia para la aproximación
"""
assert type(numero) == float, f'argumento número debe tener formato float'
assert numero >0, f'argumento número debe ser positivo'
assert type(epsilon) == float, f'argumento epsilon debe tener formato float'
assert epsilon >0, f'argumento epsilon debe ser positivo'
prueba = 1
conteo = 1
while abs(prueba**2 - numero) > epsilon:
prueba = (numero/prueba+prueba)*.5
conteo += 7
"""
1 elevar al cuadrado
1 restar numero
1 calcular abs
1 evaluar la desigualdad
1 numero/prueba
1 sumar prueba
1 multiplicar por .5
7 total de operaciones (sin contar asignaciones)
"""
print(f'Con una tolerancia de {epsilon} se usaron {conteo} cálculos para raizbiseccion')
return prueba
if __name__ == '__main__':
numero = 2.
for i in range(1,8):
epsilon=10**(-1*i)
print(raizbruta(numero,epsilon))
print(raizbiseccion(numero,epsilon))
Y estos son los resultados
con una tolerancia de 0.1 se usaron 53 cálculos para raizbruta
1.4000000000000001
Con una tolerancia de 0.1 se usaron 15 cálculos para raizbiseccion
1.4166666666666665
Con una tolerancia de 0.01 se usaron 565 cálculos para raizbruta
1.420000000000001
Con una tolerancia de 0.01 se usaron 15 cálculos para raizbiseccion
1.4166666666666665
Con una tolerancia de 0.001 se usaron 5653 cálculos para raizbruta
1.413999999999955
Con una tolerancia de 0.001 se usaron 22 cálculos para raizbiseccion
1.4142156862745097
Con una tolerancia de 0.0001 se usaron 56565 cálculos para raizbruta
1.4141999999998607
Con una tolerancia de 0.0001 se usaron 22 cálculos para raizbiseccion
1.4142156862745097
Con una tolerancia de 1e-05 se usaron 565685 cálculos para raizbruta
1.4142200000007974
Con una tolerancia de 1e-05 se usaron 22 cálculos para raizbiseccion
1.4142156862745097
Con una tolerancia de 1e-06 se usaron 5656853 cálculos para raizbruta
1.4142139999738421
Con una tolerancia de 1e-06 se usaron 29 cálculos para raizbiseccion
1.4142135623746899
Con una tolerancia de 1e-07 se usaron 56568541 cálculos para raizbruta
1.4142135999920156
Con una tolerancia de 1e-07 se usaron 29 cálculos para raizbiseccion
1.4142135623746899```
Como se ve, suponiendo que no hice mal el conteo, Cada iteración del método raizbiseccion tiene mas operaciones que las iteraciones de raizbruta. Sin embargo, el método de la bisección converge más rápido.
Cuando creas una clase e inicializas el método sin agregar “self”. El profe lo sabe.
Realice la verificación del código por parte e identifique que la función descrita en el ejemplo es:
F(x) = 1000 + X2 + 2X2
Si quisiéramos la función
F(x) = 1000 + X + X2
Deberiamos escribir:
def f(x):
respuesta = 0
for i in range(1000):
respuesta += 1
for i in range(x):
respuesta += 1
for i in range(x):
for j in range(x):
respuesta += 1
return respuesta```
Deberian ondar mas en big o talvez cereando un curso de entrevistas tecnicas donde se incluya esto creo que tienen los recursos team platzi. Pista: Pablo Trinidad Google Dev
Les dejo un link con mis apuntes https://github.com/karlbehrensg/poo-y-algoritmos-python
Conteo abstracto de operación
Con esta técnica contamos los pasos que realiza nuestro algoritmo. En el siguiente ejemplo respuesta
tendrá los números de pasos que realiza nuestro código al ejecutar.
def f(x):
respuesta = 0
for i in range(1000):
respuesta += 1
for i in range(x):
respuesta += x
for i in range(x):
for j in range(x):
respuesta += 1
respuesta += 1
return respuesta
Hola les comparto un vídeo muy interesante. Como analizar nuestros Algoritmos.
Me di cuenta que el profesor David no definió bien el polinomio. Él escribió el polinomio como
1002 + x + 2x^2
cuando debió ser
1000 + x + 2x^2
¿Porqué? Porque cuando x = 0 los términos de grado 2 y grado 1 deben ser cero, haciendo que solo se ejecute el primer loop con range(1000).
Esto es fácil de comprobar si se ejecuta el código: con x = 0 el resultado es 1000, no 1002. Y, cuando x = 1, el resultado es 1003, no 1005.
Interesante, por lo que veo básicamente estamos contando la cantidad de veces que el algoritmo va a ejecutar una operación mediante ecuaciones, es decir, contamos la cantidad de operaciones que se van a ejecutar dentro de ese algoritmo 🤔 Y gracias a esa ecuación, a medida que la variable va cambiando, podemos ver cuál es la sección del código está teniendo mayor peso, o al menos así es como lo interpreto yo 🤔
def f(x):
respuesta = 0
for i in range(1000):
respuesta += 1
for i in range(x):
respuesta += x
for i in range(x):
for j in range(x):
respuesta += 1
respuesta += 1
return respuesta```
Que fascinante!!! no sabía que los polinomios podían llegar a aplicarse de tal forma!
A re tramposo ajaa
Big O notation se utiliza en informática para describir el rendimiento o la complejidad de un algoritmo. Big O describe específicamente el peor de los casos, y se puede utilizar para describir el tiempo de ejecución requerido o el espacio utilizado (por ejemplo en la memoria en el disco) por un algoritmo.
Esto me hace recordar de la clase de analisis de algoritmos donde se calculaba el tiempo de ejecución de cada algortimo (factorial, fibonacci, algoritmos de ordenamiento, etc), por eso no me dio tan duro entender este conteo abstracto de operación.
Para calcular la raíz de 17:
Mediante Enumeración Exhaustiva se utilizaron 11 operaciones, pero no se llegó a la solución 😦
Mediante Búsqueda Binaria se utilizaron 65 operaciones y se llegó a 4.12548828125
Mediante Aproximación se emplearon 12659 y se llegó a 4.1201171875
El resultado es 4.123105626, de manera que la Búsqueda Binaria fue el método que se acercó más a la solución con menos operaciones que la Aproximación.
Es claro que hay que tomar algunas clases de matemáticas para recordar cosas y también que a este profe no le entiendo nada jajajajajajaja, es un duro mucho respeto para el, pero sus dos cursos son los que mas trabajo me ha costado entender.
Un poco de introdución a Big(o) 😮
Platzi deberían crear un curso especifico de Big O Notation!
creo que en el segundo for la respuesta debería aumentar 1 para un buen conteo, ya que el valor de respuesta sera 1+2+3+6+12+…
for i in range(x):
respuesta += 1
de esta forma ya respeta el polinomio que David propone al final
Hola a todos:
Aplicando un poco de cálculo diferencial, nos podemos dar cuenta que la función que obtuvo el profesor 2 x^(2) + x + 1002 podemos sacar la derivada de esa función que es 4x +1, y si lo graficamos veremos el cambio respeco a la función que se obtuvo.
Les recomiendo que lo grafiquen en geogebra.
Las ecuaciones dependiendo del contexto pueden tener o no diferentes tipos, esto es muy interesante por q nos dice q todo el código que ejecutemos su base es la matemáticas y tiene mucha lógica. Aquí una muestra de la solución al código de David en forma matemática
Se nota que a David le gustan las Matemáticas
Si nosotros analizamos el código :
def f(x):
respuesta = 0
for i in range(1000):
respuesta += 1
for i in range(x):
respuesta += x
for i in range(x):
for j in range(x):
respuesta += 1
respuesta += 1
return respuesta
Nos damos cuenta que el bucle
for i in range(x):
respuesta += x
Siempre retornará el valor de x al cuadrado, entonces podemos simplificar el trinomio 1000 + x + 2x² por 1000+3x² ya que quedaría 1000 + x² + 2x² y como tienen el mismo exponente lo sumamos.
El código está mal
def f(x):
contador = 0
respuesta = 0
contador += 1
for i in range(1000):
respuesta += 1
contador += 1
for i in range(x):
respuesta += 1
contador += 1
for i in range(x):
for j in range(x):
respuesta += 1
contador += 1
respuesta += 1
contador += 1
contador += 1
print(f'El valor de contador es contador: ', contador)
return respuesta
if __name__ == '__main__':
print(f'El valor de respuesta es: ', f(5))
#El valor de contador es contador: 1057
#El valor de respuesta es: 1055
contador es la representación de su polinomio 1002 + x + 2x^2
Mientras que respuesta devuelve el valor de f(x) = 1000 + x + 2x^2
Modifique el código para entenderlo paso a paso. Si lo ejecutan en la consola podrán ver que sucede.
def f(x):
respuesta = 0
print(''' EMPIEZA PRIMER LOOP ''')
for i in range(10):
respuesta += 1
print('Va de uno en uno: ' + str(respuesta))
print('Se suma de uno en uno: ' + str(respuesta))
print(''' EMPIEZA SEGUNDO LOOP ''')
for i in range(x):
print('De uno a X: ' + str(i))
respuesta += x
print('Se suma la X: ' + str(respuesta))
print(''' EMPIEZA TERCER LOOP ''')
for i in range(x):
print('LOOP PRINCIPAL DE UNO A X: ' + str(i))
# print('Es la respuesta inicial: ' + str(respuesta))
for j in range(x):
respuesta += 1
respuesta += 1
print('Empieza loop secundario: ' + str(j))
print('Se suma 2 por cada loop secundario: ' + str(respuesta))
return respuesta
if __name__ == "__main__":
f(5)```
¡Precálculo, ven a mi!
Un bucle for de Python itera sobre un objeto hasta que ese objeto está completo. Por ejemplo, puede iterar sobre el contenido de una lista o una cadena. … Uno de los tipos más comunes de bucles en Python es el bucle for. Este bucle ejecuta un bloque de código hasta que el bucle ha iterado sobre un objeto.
El bucle for de Python comienza con la palabra clave “for” seguida de un nombre de variable arbitrario, que contendrá los valores del siguiente objeto de secuencia, que se recorre por pasos.
Para los que en secundaria no recuerdan f(x) 😃
Aqui lo explican.
Using Function Notation - What is f(x)?
Ufff big O, la he visto en muchas partes, ¡vamos!
Este concepto no solo es útil para no hacer algoritmos complejos que consuman toda la memoria y tarden 100 años, sino que tambien, ya te forma para hacer algoritmos eficientes para el uso de APIs que tengan un límite de consultas.
El valor que devuelve el segundo for no es x, es x al cuadrado. Osea que nos queda 1000 + 3x^2. Igual el orden sigue siendo O(2)
aproximaciones excelente…
Muy interesante este concepto, a este nivel se vuelve importante la capacidad de realizar buenas abstracciones matemáticas de los problemas
¡Excelente clase!
Sinceramente, no entendi el objetivo de la función. Cuando corri el codigo me dio como respuesta 1003.
No entendi el parámetro de los loops, y cómo eso puede llegar a significar x^2.
Agradeceria su ayuda 😃
Me acuerdo que en geometría analítica la ingeniería nos ponían a graficar a pelo puros polinomios, con hoja de tortilla, lápiz y calculadora científica, para esto me acuerdo que con x^2 graficabas media parábola, uniendo su versión inversa graficabas una parábola, luego tambien podías crear una elipse o un círculo, es por eso que la materia, también recuerdo que en clases de matemáticas más papitas, las de finanzas o de tipo licenciado, nunca usaban exponenentes, eran puras ecuaciones de primer grado, estas son puras gráficas delíneas rectas ya dependiendo de si son positivas van en incremento o si son negativas van en decremento y recuedo que las más dificiles eran en la materia de lo inges que iban para automatización que ya eras polinomios de 3er grado para arriba y ahí si que los examentes estaban perros te daban un plano x y con una grafica senoidal y tenías que sacar el polinomio, ese tipo de graficas equivalian a por ejemplo la corriente alterna, o la fabricación de un amortiguador de un carro, etc. a que buenos tiempo cuando sabía de matebrúticas, ahora estoy bien oxidado jajaja.
def f(x):
respuesta = 0 {esto es 1}
for i in range(1000): {esto es 1000}
respuesta += 1
for i in range(x): {esto es una x)
respuesta += x
for i in range(x):
for j in range(x):
respuesta += 1 } 1
respuesta += 1 ) 1 } 2 y debido a que cada vuelta que le da j a su raango es una vuelta en el rango de i, entonces tenemos x por x } x^2 más las los operaciones de j, 2x^2
return respuesta {esto representa otro 1}
Al final tenemos un polinomio: "1002 + x + 2x^2"
Esto es una función que como ves convertimos en un polinomio de segundo graado, de esta forma nosotros podemos medir una formula en pasos con una medida abstracta de operación.
Entonces suponiendo que x es igual a 1, el polinomio se vería de esta forma, “1002+1+2”, pero si x fuese 100, entonces el polinomio se vería así “1002+100+20000”, ves?, lo que más pesó al final fue el termino de segundo grado, “2x^2” y mientras más incremente la x ese va a ser el número realmente relevante, es decir que los números que en realidad importan son los términos más grandes.
En las siguientes clases vamos a ver una medida que se llama “Big O notation”, que nos va a permitir olvidarnos de los términos que no están importando para poder analizar el crecimiento de nuestra función, pero si de los términos que nos importan: “x^2”.
Aquí les dejo esta imagen como complemento por si les interesa pero yo no suelo colocar imagenes en mis apuntes ya que no son muy confiables para dejarlas almacenadas, he tenido malas experiencias con este tipo de apuntes, y en más de una ocasión he perdido apuntes que tenia almacenados en imágenes, aparte me suelen dar problemas cuando cambio el formato de los archivos.
The first assignment operation respuesta = 0
takes constant time, so it has a time complexity of O(1)
.
The first for loop for i in range(1000)
iterates 1000 times, and the operation inside the loop respuesta += 1
takes constant time. So, the time complexity of this loop is O(1000)
.
The second for loop for i in range(x)
iterates x
times, and the operation inside the loop respuesta += x
takes constant time. So, the time complexity of this loop is O(x)
.
The nested for loops for i in range(x)
and for j in range(x)
iterate x
times each, and the operations inside the inner loop respuesta += 1
and respuesta += 1
take constant time. So, the time complexity of these nested loops is O(x * x)
, which can be simplified to O(x^2)
.
The return statement return respuesta
takes constant time, so it has a time complexity of O(1)
.
Overall, the time complexity of function f(x)
is O(1000) + O(x) + O(x^2)
, which can be simplified to O(x^2)
, since it is the term with the highest order of growth. This means that as the input size x
grows, the running time of function f(x)
grows at most as fast as x^2
def f(x):
respuesta = 0 # O(1)
for i in range(1000): # O(1000)
respuesta += 1 # O(1)
for i in range(x): # O(x)
respuesta += x # O(1)
for i in range(x): # O(x)
for j in range(x): # O(x)
respuesta += 1 # O(1)
respuesta += 1 # O(1)
return respuesta # O(1)
Solo para repasar el simbolo += :
Mis apuntes
def f(x):
respuesta = 0
for i in range(1000):
respuesta += 1
for i in range(x):
respuesta += x
for i in range(x):
for j in range(x):
respuesta += 1
respuesta += 1
return respuesta
#la formula CA = 1000 + x^2 + 2x^2
def f(x):
respuesta = 0
for i in range(1000): # 1000
respuesta += 1
for i in range(x): # x
respuesta += x
for i in range(x):
for j in range(x):
respuesta += 1 # esto seria X*X =x^2 = 2x^2
respuesta += 1
return respuesta
Buen tema.
Conteo abstracto de operación
Con esta técnica contamos los pasos que realiza nuestro algoritmo. En el siguiente ejemplo respuesta tendrá los números de pasos que realiza nuestro código al ejecutar
creditos a
https://github.com/francomanca93
def f(x):
# Primera operación
respuesta = 0
# Segunda operacion. Sin importar de x este loop correrá 1000 veces.
for i in range(1000):
respuesta += 1
# Tercera operación. Este loop correrá el valor de x
for i in range(x):
respuesta += x
# Cuarta operación. Esta parte esta corriendo 2 loop. Esto será 2x²
for i in range(x):
for j in range(x):
respuesta += 1
respuesta += 1
# Quinta operación.
return respuesta
# Respuesta
# 1002 + x + 2x²
La ecuacion que representa la cantidad de operaciones que va a ejecutar el algoritmo es:
1002 + x + 2x^2
Cuando las operaciones a ejecutar son minimas (0) el termino constante toma mayor relevancia. Mientras que a medida que aumentan las operaciones va a tomar mayor relevancia el termino elevado al cuadrado
he comprendido mucho mejor esta explicación que la de la asignatura de complejidad de la uni, aunque a decir verdad esa asignatura estaba abandonada por parte del profesorado y no es muy difícil superar su nivel xD
buen trabajo explicando muy didácticamente un tema bastante… COMPLEJO (badum tss)
tiempo con 200 mi (14.402145862579346
13.811751365661621)
Allá en la vida salvaje muchas veces tienes que medir tu código ⚡ en términos de FLOPs que son Float Operations Per Second.
Yo lo he usado en un proyecto en el que comparabamos diferentes algoritmos de cómputo en paralelo para contar tripletes de posicones.
🏎 El punto es que es básicamente esto, cuentas la cantidad de operaciones que hace tu código y cronometras con el tiempo de cpu asignado, lo divides y así puedes saber qué tantas operaciones de numeros flotantes tienes por segundo.
Algo interesante es que actualmente el hardware es capaz de operar a velocidades de TFLOPs pero lo díficil es alimentar los procesadores con los datos lo suficientemente rápido para poder aprovechar esta velocidad.
esta clase vale oro, uff importantisimo este tema.
Vaya, pense que no volveria a ver calculo, que excelente clase
mmm, 2x^2=x^2?
import time
import os
os.system ("clear")
numero = int(input('Elige un numero: '))
numero_vacio = 0
conteo = 0
inicio = time.time()
for i in range(1, numero + 1):
for j in range(1, numero + 1):
numero_vacio += 1
numero_vacio += 1
conteo += 2
final = time.time()
if final - inicio < 1:
print(f'En el ciclo hay {conteo} operaciones y se tardó {round(final - inicio, 6)} milesimas')
if final - inicio >= 1:
print(f'En el ciclo hay {conteo} operaciones y se tardó {round(final - inicio, 3)} segundos')
👍👍👍
Al final, siempre sumamos lo que es constante, para luego sumarlo, por lo que es variable.
El return, también cuenta como operación.
Un loop anidado por otro loop que itera x cantidad de veces, que suma dos cada iteración x cantidad de veces. Se puede representar como: 2x^2
Entre la función, vamos viendo lo que depende de la variable independiente y qué no.
Podemos tomar cada operación dentro de nuestras funciones, para armar nuestro crecimiento. Con lo que podemos medir su variación.
Súper interesante la clase 😃
Para los que andan perdidos
😃
Espero les ayude
Esto es similar al tema de límites en cálculo universitario?
Ustedes vieron funciones f(x) en secundaria ? 😂
Esta es la verdadera formula del codigo de la clase
Para enteder más esté tipo de conceptos les recomiendo estudiar el concepto de límite de funciones, el concepto de error por truncamiento, series de Taylor, series de McLaurin y métodos numéricos, porque al final los métodos numéricos entran en la categoría de algoritmos.
http://aprendeenlinea.udea.edu.co/lms/moodle/mod/page/view.php?id=24480
Muy interesante.
Ya hasta me entraron ganas de factorizar
Un gran concejo de Pablo Trinidad (Google Dev): “Si ustedes aprenden de Big O notation, no tengan la menor duda de que van a destacar del promedio de la industria Tech en Latinoamerica”
Sin embargo esta es una aproximación aún básica ya que no todas las operaciones consumen el mismo tiempo de ejecución. No es lo mismo realizar una operación con enteros que en punto flotante. Si se traslada el código de lenguaje humano a lenguaje máquina hay instrucciones que nosotros vemos en una línea pero para la PC toman varios ciclos.
Esto me recuerda a clases de límites indeterminados, la evaluación de que límites crecen mas que otros.
interesante clase, ver una medida para saber cual algoritmo es mejor
Si sacamos la derivada del polinomio podríamos observar de mejor manera el cambio en f(x) ante un cambio infinitesimal en x, dado el estado actual de x. Por ejemplo, la derivada es 1 + 4x, de ahí que un cambio infinitesimal en x, cuando x es 1, el cambio en f(x) es 5 (1 + 4(1)). Por tanto, aumentar el espacio de x, con el código escrito de esa manera puede reducir la eficiencia de manera considerable.
Excelente explicacion
la derivada
La ecuación de una curva positiva
super ansioso por big o 😄
matemáticas!!
Sería muy complejo hacer todo el conteo abstracto de un sistema muy grande!!!
menos mal que por la mañana hago estos cursos y por la noche estoy con los de matemáticas, así no me pierdo, en java no se necesitan matemáticas para entender, aquí si y la verdad hay que esforzarse un poquito para comprender estos conceptos entre polinomios y ecuaciones, bastante interesante todo!
Hora de sacar el polvo de mis matemáticas!!
Ya emocionado por Big(o)
yo hacia esto en ensamblador y es tedioso
Super es como limites
Está clase estuvo brutal, fue como una revelación.
Esta parte del curso me esta encantando, desde que empece a estudiar programacion siempre que escribia codigo pensaba “Esto no podra hacerse de forma mas eficiente?” y de a poco con estas lecciones estas dudas se me van resolviendo, genial todo.
def f(x):
respuesta = 0
operaciones = 0
# 1000 iteraciones siempre
for i in range(1000):
respuesta += 1
operaciones += 1
# x iteraciones
for i in range(x):
respuesta += x
operaciones += 1
# x**2 iteraciones por 2 operaciones cada iteracion >>> 2x**2
for i in range(x):
for j in range(x):
respuesta += 1
respuesta += 1
operaciones += 1
print(
f'Se realizaron {operaciones} operaciones de las {2 * x**2 + x + 1000} esperadas')
return respuesta
def main():
for n in range(50):
print(f'f({n}) : ')
print(f'f de {n} = {f(n)}')
if __name__ == '__main__':
main()
Para ahondar en este tema, así como resolver problemas y preguntas tipo entrevista, hay un libro que es bastante útil. “cracking the coding interview”. Espero les sea de ayuda, saludos.
Esta clase sola ya hace que me sienta contento de haber comprado Platzi
Se empieza aponer complejo y me gusta
Conteo abstracto de operaciones
Contamos todas las operaciones que realiza el código para tratar de determinar su complejidad.
Para hacer un conteo abstracto de la eficiencia de una función vamos a contar cada vez que se tiene que hacer una operación.
Vamos a contar el número de operaciones en el siguiente algoritmo.
def f(x):
# 1 operacion
respuesta = 0
# 1000 operaciones
for i in range(1000):
respuesta += 1
# x operaciones
for i in range(x):
respuesta += x
for i in range(x):
for i in range(x):
# Como aquí hay una iteración dentro de otra, esto va a multiplicar las 2 operaciones por x * x = 2x^2
respuesta += 1
respuesta += 1
# 1 operación
return respuesta
Si sumamos todo al final obtenemos 1002 + x + x^2
lo cual es una buena aproximación, sin embargo cuando nos aproximamos a una x cerca del infinito, los términos que podrían parecer mas afectar a la velocidad de este algoritmo como el 1002, dejan de hacer sentido y nos distraen de lo que en realidad va a ser lo mas pesado como la x cuadrada
Tiempo que ha tardado mi ordenador en completar un millon
def f(x) → la función
answer = 0 → 1 operación
for i in range(1000): → 1,000 operaciones
answer += 1
for i in range(x): → X operaciones
answer += x
for i in range(x):
for j in range (x):
answer += 1 —> XX operaciones (cada for es una X)*
answer += 1 —> XX operaciones (cada for es una X)*
return answer → 1 operación
Sumando
1 + 1000 + 1 = 1002
X + XX + XX = X + 2X^2
Tiempo de la fórmula → 1002 + X + 2X^2
Lo que va a tener más impacto a la larga es exponente más grande entonces:
Expresado en Big O→ O(n^2)
Cuando veo estas clases me da la alegría de avanzar y por otro lado siento pena por no haber tenido grandes profesores de matemáticas que me hayan hecho amar esta disciplina y las ciencias formales.
¿Quieres ver más aportes, preguntas y respuestas de la comunidad?