R Notebook
Ejercicio 3
Calcular la complejidad temporal del algoritmo para el siguiente algoritmo de forma experimental. El cálculo se debe efectuar para los siguiente intervalos de la variable monto
- Calcular la complejidad para el intervalo (1,100) con paso 10
- Calcular la complejidad para el intervalo (100,1000) con paso 100
- Calcular la complejidad para el intervalo (1000,10000) con paso 1000
- Calcular la complejidad para el intervalo (10000,100000) con paso 10000
- Calcular la complejidad para el intervalo (100000,1000000) con paso 100000
def contar_billetes_2(monto):
start=time.time()
billete=100
inc=0
billete_actual=billete/(10**inc)
while (monto>0):
if monto >= billete_actual:
monto=monto-billete_actual
# print ("1 billete de ",billete_actual)
else:
inc=inc+1
billete_actual=billete/(10**inc)
stop=time.time()
return(stop-start)
import sys,time
for monto in range(10,100,10):
print monto,contar_billetes_2(monto)
#
for monto in range(100,1000,100):
print monto,contar_billetes_2(monto)
#
for monto in range(1000,10000,1000):
print monto,contar_billetes_2(monto)
#
for monto in range(10000,100000,10000):
print monto,contar_billetes_2(monto)
#
for monto in range(100000,1000000,100000):
print monto,contar_billetes_2(monto)
10 5.00679016113e-06
20 9.53674316406e-07
30 9.53674316406e-07
40 1.19209289551e-06
50 9.53674316406e-07
60 9.53674316406e-07
70 1.19209289551e-06
80 9.53674316406e-07
90 1.19209289551e-06
100 9.53674316406e-07
200 9.53674316406e-07
300 0.0
400 9.53674316406e-07
500 0.0
600 9.53674316406e-07
700 1.19209289551e-06
800 9.53674316406e-07
900 9.53674316406e-07
1000 1.19209289551e-06
2000 1.90734863281e-06
3000 2.86102294922e-06
4000 2.86102294922e-06
5000 2.86102294922e-06
6000 5.00679016113e-06
7000 4.05311584473e-06
8000 5.00679016113e-06
9000 6.19888305664e-06
10000 7.15255737305e-06
20000 1.19209289551e-05
30000 1.78813934326e-05
40000 2.47955322266e-05
50000 3.00407409668e-05
60000 3.79085540771e-05
70000 4.29153442383e-05
80000 4.10079956055e-05
90000 4.6968460083e-05
100000 5.19752502441e-05
200000 0.000103950500488
300000 0.000154972076416
400000 0.00020694732666
500000 0.000258922576904
600000 0.000310897827148
700000 0.000364065170288
800000 0.000414133071899
900000 0.000466108322144Proyectar los resultados obtenidos sobre un eje de coordenadas cartesianos donde el eje X representa la el tamaño de la entrada (n) y el eje Y el tiempo de ejecución para cada uno de los intervalos
LS0tCnRpdGxlOiAiUiBOb3RlYm9vayIKb3V0cHV0OiBodG1sX25vdGVib29rCi0tLQoKCiMjIyBFamVyY2ljaW8gMwpDYWxjdWxhciBsYSBjb21wbGVqaWRhZCB0ZW1wb3JhbCBkZWwgYWxnb3JpdG1vICBwYXJhIGVsIHNpZ3VpZW50ZSBhbGdvcml0bW8gZGUgZm9ybWEgZXhwZXJpbWVudGFsLiAgRWwgY8OhbGN1bG8gc2UgZGViZSBlZmVjdHVhciBwYXJhIGxvcyBzaWd1aWVudGUgaW50ZXJ2YWxvcyBkZSBsYSB2YXJpYWJsZSBtb250bwoKMS4gQ2FsY3VsYXIgbGEgY29tcGxlamlkYWQgcGFyYSBlbCBpbnRlcnZhbG8gKDEsMTAwKSBjb24gcGFzbyAxMAoyLiBDYWxjdWxhciBsYSBjb21wbGVqaWRhZCBwYXJhIGVsIGludGVydmFsbyAoMTAwLDEwMDApIGNvbiBwYXNvIDEwMAozLiBDYWxjdWxhciBsYSBjb21wbGVqaWRhZCBwYXJhIGVsIGludGVydmFsbyAoMTAwMCwxMDAwMCkgY29uIHBhc28gMTAwMAo0LiBDYWxjdWxhciBsYSBjb21wbGVqaWRhZCBwYXJhIGVsIGludGVydmFsbyAoMTAwMDAsMTAwMDAwKSBjb24gcGFzbyAxMDAwMAo1LiBDYWxjdWxhciBsYSBjb21wbGVqaWRhZCBwYXJhIGVsIGludGVydmFsbyAoMTAwMDAwLDEwMDAwMDApIGNvbiBwYXNvIDEwMDAwMAoKCmBgYHtweXRob259CiMgQWxnb3JpdG1vIGluw7p0aWwgcXVlIHJlc3RhIGJpbGxldGVzIGRlIDEwMCwxMCB5IDEgYSB1biBtb250byBkYWRvLgpkZWYgZW50cmVnYV9iaWxsZXRlc18yKG1vbnRvKToKICAgICAgICBzdGFydD10aW1lLnRpbWUoKQogICAgICAgIGJpbGxldGU9MTAwCiAgICAgICAgaW5jPTAKICAgICAgICBiaWxsZXRlX2FjdHVhbD1iaWxsZXRlLygxMCoqaW5jKQogICAgICAgIHdoaWxlIChtb250bz4wKToKICAgICAgICAgICAgICAgIGlmIG1vbnRvID49IGJpbGxldGVfYWN0dWFsOgogICAgICAgICAgICAgICAgICAgICAgICBtb250bz1tb250by1iaWxsZXRlX2FjdHVhbAogICAgICAgICAgICAgICAgIyAgICAgICBwcmludCAoIjEgYmlsbGV0ZSBkZSAiLGJpbGxldGVfYWN0dWFsKQogICAgICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgICAgICAgICAgaW5jPWluYysxCiAgICAgICAgICAgICAgICAgICAgICAgIGJpbGxldGVfYWN0dWFsPWJpbGxldGUvKDEwKippbmMpCiAgICAgICAgc3RvcD10aW1lLnRpbWUoKQogICAgICAgIHJldHVybihzdG9wLXN0YXJ0KQoKCgppbXBvcnQgc3lzLHRpbWUKZm9yIG1vbnRvIGluIHJhbmdlKDEwLDEwMCwxMCk6CiAgICAgICAgcHJpbnQgbW9udG8sZW50cmVnYV9iaWxsZXRlc18yKG1vbnRvKQojCmZvciBtb250byBpbiByYW5nZSgxMDAsMTAwMCwxMDApOgogICAgICAgIHByaW50IG1vbnRvLGVudHJlZ2FfYmlsbGV0ZXNfMihtb250bykKIwpmb3IgbW9udG8gaW4gcmFuZ2UoMTAwMCwxMDAwMCwxMDAwKToKICAgICAgICBwcmludCBtb250byxlbnRyZWdhX2JpbGxldGVzXzIobW9udG8pCiMKZm9yIG1vbnRvIGluIHJhbmdlKDEwMDAwLDEwMDAwMCwxMDAwMCk6CiAgICAgICAgcHJpbnQgbW9udG8sZW50cmVnYV9iaWxsZXRlc18yKG1vbnRvKQojCmZvciBtb250byBpbiByYW5nZSgxMDAwMDAsMTAwMDAwMCwxMDAwMDApOgogICAgICAgIHByaW50IG1vbnRvLGVudHJlZ2FfYmlsbGV0ZXNfMihtb250bykKCmBgYAoKUHJveWVjdGFyIGxvcyByZXN1bHRhZG9zIG9idGVuaWRvcyBzb2JyZSB1biBlamUgZGUgY29vcmRlbmFkYXMgY2FydGVzaWFub3MgZG9uZGUgZWwgZWplIFggcmVwcmVzZW50YSBsYSBlbCB0YW1hw7FvIGRlIGxhIGVudHJhZGEgKG4pIHkgZWwgZWplIFkgZWwgdGllbXBvIGRlIGVqZWN1Y2nDs24gcGFyYSBjYWRhIHVubyBkZSBsb3MgaW50ZXJ2YWxvcwoKCgpgYGB7ciwgZWNobz1GQUxTRSwgZmlnLmhlaWdodD0xMiwgZmlnLndpZHRoPTV9CmxpYnJhcnkoZ3JpZEV4dHJhKQpkYXRhPC1yZWFkLmNzdigiL2hvbWUvaGFycG8vZGF0YS5jc3YiLGhlYWRlciA9IEYsc2VwPScgJykKCmkxPC1nZ3Bsb3QoZGF0YVsxOjEwLF0pKwogIGdlb21fbGluZShhZXMoeD1WMSx5PVYyKjEwMDApKSsKICB5bGFiKCJ0aW1lIFttc10iKSt4bGFiKCJuIikrZ2d0aXRsZSgiaW50ZXJ2YWxvICgxLDEwMCkgY29uIHBhc28gMTAiKSsKICB0aGVtZV9idygpCgppMjwtZ2dwbG90KGRhdGFbMTE6MjAsXSkrCiAgZ2VvbV9saW5lKGFlcyh4PVYxLHk9VjIqMTAwMCkpKwogIHlsYWIoInRpbWUgW21zXSIpK3hsYWIoIm4iKStnZ3RpdGxlKCJpbnRlcnZhbG8gKDEwMCwxMDAwKSBjb24gcGFzbyAxMDAiKSsKICB0aGVtZV9idygpCgppMzwtZ2dwbG90KGRhdGFbMjE6MzAsXSkrCiAgZ2VvbV9saW5lKGFlcyh4PVYxLHk9VjIqMTAwMCkpKwogIHlsYWIoInRpbWUgW21zXSIpK3hsYWIoIm4iKStnZ3RpdGxlKCJpbnRlcnZhbG8gKDEwMDAsMTAwMDApIGNvbiBwYXNvIDEwMDAiKSsKICB0aGVtZV9idygpCgppNDwtZ2dwbG90KGRhdGFbMzE6NDAsXSkrCiAgZ2VvbV9saW5lKGFlcyh4PVYxLHk9VjIqMTAwMCkpKwogIHlsYWIoInRpbWUgW21zXSIpK3hsYWIoIm4iKStnZ3RpdGxlKCJpbnRlcnZhbG8gKDEwMDAwLDEwMDAwMCkgY29uIHBhc28gMTAwMDAiKSsKICB0aGVtZV9idygpCgppNTwtZ2dwbG90KGRhdGFbNDE6NTAsXSkrCiAgZ2VvbV9saW5lKGFlcyh4PVYxLHk9VjIqMTAwMCkpKwogIHlsYWIoInRpbWUgW21zXSIpK3hsYWIoIm4iKStnZ3RpdGxlKCJpbnRlcnZhbG8gKDEwMDAwMCwxMDAwMDAwKSBjb24gcGFzbyAxMDAwMDAiKSsKICB0aGVtZV9idygpCgpncmlkLmFycmFuZ2UoaTEsaTIsaTMsaTQsaTUsbmNvbD0xKQpgYGAKCg==