análisis de algoritmos - unamgil/2020-1/_downloads/2... · análisis de algoritmos. ... •la...

12
Análisis de Algoritmos

Upload: others

Post on 03-Aug-2020

2 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: Análisis de Algoritmos - UNAMgil/2020-1/_downloads/2... · Análisis de Algoritmos. ... •La solución más sencilla no siempre es la más eficiente •Los algoritmos eficientes

Análisis de Algoritmos

Page 2: Análisis de Algoritmos - UNAMgil/2020-1/_downloads/2... · Análisis de Algoritmos. ... •La solución más sencilla no siempre es la más eficiente •Los algoritmos eficientes

Diseño e implementación de un programa

•Un programa debe producir resultados correctos

•En algunos casos el desempeño es un aspecto importante de correctez

Page 3: Análisis de Algoritmos - UNAMgil/2020-1/_downloads/2... · Análisis de Algoritmos. ... •La solución más sencilla no siempre es la más eficiente •Los algoritmos eficientes

•Escribir programas eficientes no es fácil

•La solución más sencilla no siempre es la más eficiente

•Los algoritmos eficientes generalmente usan técnicas sutiles que los hace un poco más difíciles de entender

Page 4: Análisis de Algoritmos - UNAMgil/2020-1/_downloads/2... · Análisis de Algoritmos. ... •La solución más sencilla no siempre es la más eficiente •Los algoritmos eficientes

¿Cómo comparar dos programas (algoritmos)?

¿Qué necesitamos para comparar?

¿Qué tal por el tiempo de ejecución?

Page 5: Análisis de Algoritmos - UNAMgil/2020-1/_downloads/2... · Análisis de Algoritmos. ... •La solución más sencilla no siempre es la más eficiente •Los algoritmos eficientes

def factorial(n): respuesta = 1 while n > 1: respuesta = respuesta * n n = n - 1 return respuesta

• Velocidad de la computadora

• Eficiencias de la implementación del lenguaje (python)

• El valor de la entrada

Page 6: Análisis de Algoritmos - UNAMgil/2020-1/_downloads/2... · Análisis de Algoritmos. ... •La solución más sencilla no siempre es la más eficiente •Los algoritmos eficientes

• Velocidad de la computadora

• Eficiencias de la implementación del lenguaje (python)

• El valor de la entrada

def factorial(n): respuesta = 1 while n > 1: respuesta = respuesta * n n = n - 1 return respuesta

• Medimos el tiempo en base al número de operaciones básicas

• Expresamos el tiempo en términos del tamaño de la entrada

Page 7: Análisis de Algoritmos - UNAMgil/2020-1/_downloads/2... · Análisis de Algoritmos. ... •La solución más sencilla no siempre es la más eficiente •Los algoritmos eficientes

Cuando calculamos la complejidad de un algoritmo se considera

•Peor caso - Usa la entrada que da el desempeño más lento.

•Mejor caso - Usa la entrada que da los mejores resultados

•Caso promedio - entrada aleatoria

Page 8: Análisis de Algoritmos - UNAMgil/2020-1/_downloads/2... · Análisis de Algoritmos. ... •La solución más sencilla no siempre es la más eficiente •Los algoritmos eficientes

def factorial(n): respuesta = 1 while n > 1: respuesta = respuesta * n n = n - 1 return respuesta

2 + 5n<latexit sha1_base64="H2mCLlcvpDEkzBVUdDnyxudzLw8=">AAAB73icbVDLSgNBEOyNrxhfUY9eBhNBEMJuQPQY9OIxgnlAsoTZyWwyZHZ2nekVQshPePGgiFd/x5t/4yTZgyYWNBRV3XR3BYkUBl3328mtrW9sbuW3Czu7e/sHxcOjpolTzXiDxTLW7YAaLoXiDRQoeTvRnEaB5K1gdDvzW09cGxGrBxwn3I/oQIlQMIpWaper5IJcqnKvWHIr7hxklXgZKUGGeq/41e3HLI24QiapMR3PTdCfUI2CST4tdFPDE8pGdMA7lioaceNP5vdOyZlV+iSMtS2FZK7+npjQyJhxFNjOiOLQLHsz8T+vk2J47U+ESlLkii0WhakkGJPZ86QvNGcox5ZQpoW9lbAh1ZShjahgQ/CWX14lzWrFcyvefbVUu8niyMMJnMI5eHAFNbiDOjSAgYRneIU359F5cd6dj0VrzslmjuEPnM8fiRiOUA==</latexit><latexit sha1_base64="H2mCLlcvpDEkzBVUdDnyxudzLw8=">AAAB73icbVDLSgNBEOyNrxhfUY9eBhNBEMJuQPQY9OIxgnlAsoTZyWwyZHZ2nekVQshPePGgiFd/x5t/4yTZgyYWNBRV3XR3BYkUBl3328mtrW9sbuW3Czu7e/sHxcOjpolTzXiDxTLW7YAaLoXiDRQoeTvRnEaB5K1gdDvzW09cGxGrBxwn3I/oQIlQMIpWaper5IJcqnKvWHIr7hxklXgZKUGGeq/41e3HLI24QiapMR3PTdCfUI2CST4tdFPDE8pGdMA7lioaceNP5vdOyZlV+iSMtS2FZK7+npjQyJhxFNjOiOLQLHsz8T+vk2J47U+ESlLkii0WhakkGJPZ86QvNGcox5ZQpoW9lbAh1ZShjahgQ/CWX14lzWrFcyvefbVUu8niyMMJnMI5eHAFNbiDOjSAgYRneIU359F5cd6dj0VrzslmjuEPnM8fiRiOUA==</latexit><latexit sha1_base64="H2mCLlcvpDEkzBVUdDnyxudzLw8=">AAAB73icbVDLSgNBEOyNrxhfUY9eBhNBEMJuQPQY9OIxgnlAsoTZyWwyZHZ2nekVQshPePGgiFd/x5t/4yTZgyYWNBRV3XR3BYkUBl3328mtrW9sbuW3Czu7e/sHxcOjpolTzXiDxTLW7YAaLoXiDRQoeTvRnEaB5K1gdDvzW09cGxGrBxwn3I/oQIlQMIpWaper5IJcqnKvWHIr7hxklXgZKUGGeq/41e3HLI24QiapMR3PTdCfUI2CST4tdFPDE8pGdMA7lioaceNP5vdOyZlV+iSMtS2FZK7+npjQyJhxFNjOiOLQLHsz8T+vk2J47U+ESlLkii0WhakkGJPZ86QvNGcox5ZQpoW9lbAh1ZShjahgQ/CWX14lzWrFcyvefbVUu8niyMMJnMI5eHAFNbiDOjSAgYRneIU359F5cd6dj0VrzslmjuEPnM8fiRiOUA==</latexit><latexit sha1_base64="H2mCLlcvpDEkzBVUdDnyxudzLw8=">AAAB73icbVDLSgNBEOyNrxhfUY9eBhNBEMJuQPQY9OIxgnlAsoTZyWwyZHZ2nekVQshPePGgiFd/x5t/4yTZgyYWNBRV3XR3BYkUBl3328mtrW9sbuW3Czu7e/sHxcOjpolTzXiDxTLW7YAaLoXiDRQoeTvRnEaB5K1gdDvzW09cGxGrBxwn3I/oQIlQMIpWaper5IJcqnKvWHIr7hxklXgZKUGGeq/41e3HLI24QiapMR3PTdCfUI2CST4tdFPDE8pGdMA7lioaceNP5vdOyZlV+iSMtS2FZK7+npjQyJhxFNjOiOLQLHsz8T+vk2J47U+ESlLkii0WhakkGJPZ86QvNGcox5ZQpoW9lbAh1ZShjahgQ/CWX14lzWrFcyvefbVUu8niyMMJnMI5eHAFNbiDOjSAgYRneIU359F5cd6dj0VrzslmjuEPnM8fiRiOUA==</latexit>

n = 1000<latexit sha1_base64="bEVRbPW9HvTt2e0+ek+kHhVEmz8=">AAAB8nicbVBNS8NAEJ3Ur1q/qh69LDaCp7LpRS9C0YvHCvYD0lA22027dLMJuxuhhP4MLx4U8eqv8ea/cdvmoK0PBh7vzTAzL0wF1wbjb6e0sbm1vVPereztHxweVY9POjrJFGVtmohE9UKimeCStQ03gvVSxUgcCtYNJ3dzv/vElOaJfDTTlAUxGUkecUqMlXzXlejGwxi77qBaw3W8AFonXkFqUKA1qH71hwnNYiYNFURr38OpCXKiDKeCzSr9TLOU0AkZMd9SSWKmg3xx8gxdWGWIokTZkgYt1N8TOYm1nsah7YyJGetVby7+5/mZia6DnMs0M0zS5aIoE8gkaP4/GnLFqBFTSwhV3N6K6JgoQo1NqWJD8FZfXiedRt3Dde+hUWveFnGU4QzO4RI8uIIm3EML2kAhgWd4hTfHOC/Ou/OxbC05xcwp/IHz+QPe2o8C</latexit><latexit sha1_base64="bEVRbPW9HvTt2e0+ek+kHhVEmz8=">AAAB8nicbVBNS8NAEJ3Ur1q/qh69LDaCp7LpRS9C0YvHCvYD0lA22027dLMJuxuhhP4MLx4U8eqv8ea/cdvmoK0PBh7vzTAzL0wF1wbjb6e0sbm1vVPereztHxweVY9POjrJFGVtmohE9UKimeCStQ03gvVSxUgcCtYNJ3dzv/vElOaJfDTTlAUxGUkecUqMlXzXlejGwxi77qBaw3W8AFonXkFqUKA1qH71hwnNYiYNFURr38OpCXKiDKeCzSr9TLOU0AkZMd9SSWKmg3xx8gxdWGWIokTZkgYt1N8TOYm1nsah7YyJGetVby7+5/mZia6DnMs0M0zS5aIoE8gkaP4/GnLFqBFTSwhV3N6K6JgoQo1NqWJD8FZfXiedRt3Dde+hUWveFnGU4QzO4RI8uIIm3EML2kAhgWd4hTfHOC/Ou/OxbC05xcwp/IHz+QPe2o8C</latexit><latexit sha1_base64="bEVRbPW9HvTt2e0+ek+kHhVEmz8=">AAAB8nicbVBNS8NAEJ3Ur1q/qh69LDaCp7LpRS9C0YvHCvYD0lA22027dLMJuxuhhP4MLx4U8eqv8ea/cdvmoK0PBh7vzTAzL0wF1wbjb6e0sbm1vVPereztHxweVY9POjrJFGVtmohE9UKimeCStQ03gvVSxUgcCtYNJ3dzv/vElOaJfDTTlAUxGUkecUqMlXzXlejGwxi77qBaw3W8AFonXkFqUKA1qH71hwnNYiYNFURr38OpCXKiDKeCzSr9TLOU0AkZMd9SSWKmg3xx8gxdWGWIokTZkgYt1N8TOYm1nsah7YyJGetVby7+5/mZia6DnMs0M0zS5aIoE8gkaP4/GnLFqBFTSwhV3N6K6JgoQo1NqWJD8FZfXiedRt3Dde+hUWveFnGU4QzO4RI8uIIm3EML2kAhgWd4hTfHOC/Ou/OxbC05xcwp/IHz+QPe2o8C</latexit><latexit sha1_base64="hP+6LrUf2d3tZaldqaQQvEKMXyw=">AAAB2XicbZDNSgMxFIXv1L86Vq1rN8EiuCozbnQpuHFZwbZCO5RM5k4bmskMyR2hDH0BF25EfC93vo3pz0JbDwQ+zknIvSculLQUBN9ebWd3b/+gfugfNfzjk9Nmo2fz0gjsilzl5jnmFpXU2CVJCp8LgzyLFfbj6f0i77+gsTLXTzQrMMr4WMtUCk7O6oyaraAdLMW2IVxDC9YaNb+GSS7KDDUJxa0dhEFBUcUNSaFw7g9LiwUXUz7GgUPNM7RRtRxzzi6dk7A0N+5oYkv394uKZ9bOstjdzDhN7Ga2MP/LBiWlt1EldVESarH6KC0Vo5wtdmaJNChIzRxwYaSblYkJN1yQa8Z3HYSbG29D77odBu3wMYA6nMMFXEEIN3AHD9CBLghI4BXevYn35n2suqp569LO4I+8zx84xIo4</latexit><latexit sha1_base64="TzBCjhn8wNZoeqRs62J1iK7e21Y=">AAAB53icbZBLSwMxFIXv1FetVatbN8GO4Kpk3OhGENy4rGAf0A4lk2ba0ExmSO4IZejPcONCEf+RO/+N6WOhrQcCH+ck5N4TZUpapPTbK21t7+zulfcrB9XDo+PaSbVt09xw0eKpSk03YlYoqUULJSrRzYxgSaREJ5rcz/POszBWpvoJp5kIEzbSMpacobN6vq/JbUAp9f1BrU4bdCGyCcEK6rBSc1D76g9TnidCI1fM2l5AMwwLZlByJWaVfm5FxviEjUTPoWaJsGGxGHlGLpwzJHFq3NFIFu7vFwVLrJ0mkbuZMBzb9Wxu/pf1coxvwkLqLEeh+fKjOFcEUzLfnwylERzV1AHjRrpZCR8zwzi6liquhGB95U1oXzUC2ggeKZThDM7hEgK4hjt4gCa0gEMKL/AG7x56r97Hsq6St+rtFP7I+/wBtkiNpw==</latexit><latexit sha1_base64="TzBCjhn8wNZoeqRs62J1iK7e21Y=">AAAB53icbZBLSwMxFIXv1FetVatbN8GO4Kpk3OhGENy4rGAf0A4lk2ba0ExmSO4IZejPcONCEf+RO/+N6WOhrQcCH+ck5N4TZUpapPTbK21t7+zulfcrB9XDo+PaSbVt09xw0eKpSk03YlYoqUULJSrRzYxgSaREJ5rcz/POszBWpvoJp5kIEzbSMpacobN6vq/JbUAp9f1BrU4bdCGyCcEK6rBSc1D76g9TnidCI1fM2l5AMwwLZlByJWaVfm5FxviEjUTPoWaJsGGxGHlGLpwzJHFq3NFIFu7vFwVLrJ0mkbuZMBzb9Wxu/pf1coxvwkLqLEeh+fKjOFcEUzLfnwylERzV1AHjRrpZCR8zwzi6liquhGB95U1oXzUC2ggeKZThDM7hEgK4hjt4gCa0gEMKL/AG7x56r97Hsq6St+rtFP7I+/wBtkiNpw==</latexit><latexit sha1_base64="ZcPVZUmFBxFyVWfwSsWYCK4XrN0=">AAAB8nicbVBNSwMxEJ31s9avqkcvwa7gqWS96EUoevFYwX7AdinZNNuGZpMlyQql9Gd48aCIV3+NN/+NabsHbX0w8Hhvhpl5cSa4sRh/e2vrG5tb26Wd8u7e/sFh5ei4ZVSuKWtSJZTuxMQwwSVrWm4F62SakTQWrB2P7mZ++4lpw5V8tOOMRSkZSJ5wSqyTQt+X6CbAGPt+r1LFNTwHWiVBQapQoNGrfHX7iuYpk5YKYkwY4MxGE6Itp4JNy93csIzQERmw0FFJUmaiyfzkKTp3Sh8lSruSFs3V3xMTkhozTmPXmRI7NMveTPzPC3ObXEcTLrPcMkkXi5JcIKvQ7H/U55pRK8aOEKq5uxXRIdGEWpdS2YUQLL+8SlqXtQDXggdcrd8WcZTgFM7gAgK4gjrcQwOaQEHBM7zCm2e9F+/d+1i0rnnFzAn8gff5A946jwA=</latexit><latexit sha1_base64="bEVRbPW9HvTt2e0+ek+kHhVEmz8=">AAAB8nicbVBNS8NAEJ3Ur1q/qh69LDaCp7LpRS9C0YvHCvYD0lA22027dLMJuxuhhP4MLx4U8eqv8ea/cdvmoK0PBh7vzTAzL0wF1wbjb6e0sbm1vVPereztHxweVY9POjrJFGVtmohE9UKimeCStQ03gvVSxUgcCtYNJ3dzv/vElOaJfDTTlAUxGUkecUqMlXzXlejGwxi77qBaw3W8AFonXkFqUKA1qH71hwnNYiYNFURr38OpCXKiDKeCzSr9TLOU0AkZMd9SSWKmg3xx8gxdWGWIokTZkgYt1N8TOYm1nsah7YyJGetVby7+5/mZia6DnMs0M0zS5aIoE8gkaP4/GnLFqBFTSwhV3N6K6JgoQo1NqWJD8FZfXiedRt3Dde+hUWveFnGU4QzO4RI8uIIm3EML2kAhgWd4hTfHOC/Ou/OxbC05xcwp/IHz+QPe2o8C</latexit><latexit sha1_base64="bEVRbPW9HvTt2e0+ek+kHhVEmz8=">AAAB8nicbVBNS8NAEJ3Ur1q/qh69LDaCp7LpRS9C0YvHCvYD0lA22027dLMJuxuhhP4MLx4U8eqv8ea/cdvmoK0PBh7vzTAzL0wF1wbjb6e0sbm1vVPereztHxweVY9POjrJFGVtmohE9UKimeCStQ03gvVSxUgcCtYNJ3dzv/vElOaJfDTTlAUxGUkecUqMlXzXlejGwxi77qBaw3W8AFonXkFqUKA1qH71hwnNYiYNFURr38OpCXKiDKeCzSr9TLOU0AkZMd9SSWKmg3xx8gxdWGWIokTZkgYt1N8TOYm1nsah7YyJGetVby7+5/mZia6DnMs0M0zS5aIoE8gkaP4/GnLFqBFTSwhV3N6K6JgoQo1NqWJD8FZfXiedRt3Dde+hUWveFnGU4QzO4RI8uIIm3EML2kAhgWd4hTfHOC/Ou/OxbC05xcwp/IHz+QPe2o8C</latexit><latexit sha1_base64="bEVRbPW9HvTt2e0+ek+kHhVEmz8=">AAAB8nicbVBNS8NAEJ3Ur1q/qh69LDaCp7LpRS9C0YvHCvYD0lA22027dLMJuxuhhP4MLx4U8eqv8ea/cdvmoK0PBh7vzTAzL0wF1wbjb6e0sbm1vVPereztHxweVY9POjrJFGVtmohE9UKimeCStQ03gvVSxUgcCtYNJ3dzv/vElOaJfDTTlAUxGUkecUqMlXzXlejGwxi77qBaw3W8AFonXkFqUKA1qH71hwnNYiYNFURr38OpCXKiDKeCzSr9TLOU0AkZMd9SSWKmg3xx8gxdWGWIokTZkgYt1N8TOYm1nsah7YyJGetVby7+5/mZia6DnMs0M0zS5aIoE8gkaP4/GnLFqBFTSwhV3N6K6JgoQo1NqWJD8FZfXiedRt3Dde+hUWveFnGU4QzO4RI8uIIm3EML2kAhgWd4hTfHOC/Ou/OxbC05xcwp/IHz+QPe2o8C</latexit><latexit sha1_base64="bEVRbPW9HvTt2e0+ek+kHhVEmz8=">AAAB8nicbVBNS8NAEJ3Ur1q/qh69LDaCp7LpRS9C0YvHCvYD0lA22027dLMJuxuhhP4MLx4U8eqv8ea/cdvmoK0PBh7vzTAzL0wF1wbjb6e0sbm1vVPereztHxweVY9POjrJFGVtmohE9UKimeCStQ03gvVSxUgcCtYNJ3dzv/vElOaJfDTTlAUxGUkecUqMlXzXlejGwxi77qBaw3W8AFonXkFqUKA1qH71hwnNYiYNFURr38OpCXKiDKeCzSr9TLOU0AkZMd9SSWKmg3xx8gxdWGWIokTZkgYt1N8TOYm1nsah7YyJGetVby7+5/mZia6DnMs0M0zS5aIoE8gkaP4/GnLFqBFTSwhV3N6K6JgoQo1NqWJD8FZfXiedRt3Dde+hUWveFnGU4QzO4RI8uIIm3EML2kAhgWd4hTfHOC/Ou/OxbC05xcwp/IHz+QPe2o8C</latexit><latexit sha1_base64="bEVRbPW9HvTt2e0+ek+kHhVEmz8=">AAAB8nicbVBNS8NAEJ3Ur1q/qh69LDaCp7LpRS9C0YvHCvYD0lA22027dLMJuxuhhP4MLx4U8eqv8ea/cdvmoK0PBh7vzTAzL0wF1wbjb6e0sbm1vVPereztHxweVY9POjrJFGVtmohE9UKimeCStQ03gvVSxUgcCtYNJ3dzv/vElOaJfDTTlAUxGUkecUqMlXzXlejGwxi77qBaw3W8AFonXkFqUKA1qH71hwnNYiYNFURr38OpCXKiDKeCzSr9TLOU0AkZMd9SSWKmg3xx8gxdWGWIokTZkgYt1N8TOYm1nsah7YyJGetVby7+5/mZia6DnMs0M0zS5aIoE8gkaP4/GnLFqBFTSwhV3N6K6JgoQo1NqWJD8FZfXiedRt3Dde+hUWveFnGU4QzO4RI8uIIm3EML2kAhgWd4hTfHOC/Ou/OxbC05xcwp/IHz+QPe2o8C</latexit><latexit sha1_base64="bEVRbPW9HvTt2e0+ek+kHhVEmz8=">AAAB8nicbVBNS8NAEJ3Ur1q/qh69LDaCp7LpRS9C0YvHCvYD0lA22027dLMJuxuhhP4MLx4U8eqv8ea/cdvmoK0PBh7vzTAzL0wF1wbjb6e0sbm1vVPereztHxweVY9POjrJFGVtmohE9UKimeCStQ03gvVSxUgcCtYNJ3dzv/vElOaJfDTTlAUxGUkecUqMlXzXlejGwxi77qBaw3W8AFonXkFqUKA1qH71hwnNYiYNFURr38OpCXKiDKeCzSr9TLOU0AkZMd9SSWKmg3xx8gxdWGWIokTZkgYt1N8TOYm1nsah7YyJGetVby7+5/mZia6DnMs0M0zS5aIoE8gkaP4/GnLFqBFTSwhV3N6K6JgoQo1NqWJD8FZfXiedRt3Dde+hUWveFnGU4QzO4RI8uIIm3EML2kAhgWd4hTfHOC/Ou/OxbC05xcwp/IHz+QPe2o8C</latexit>

2 + 5n = 5002<latexit sha1_base64="AJ/s1LoL6XKHzadZBoovA/hpsRc=">AAAB+HicbVBNS8NAEJ34WetHox69LLaCIJQkUPQiFL14rGA/oA1ls920SzebsLsRaugv8eJBEa/+FG/+G7dtDtr6YODx3gwz84KEM6Ud59taW9/Y3Nou7BR39/YPSvbhUUvFqSS0SWIey06AFeVM0KZmmtNOIimOAk7bwfh25rcfqVQsFg96klA/wkPBQkawNlLfLlU8dIFqAl2jmuN4lb5ddqrOHGiVuDkpQ45G3/7qDWKSRlRowrFSXddJtJ9hqRnhdFrspYommIzxkHYNFTiiys/mh0/RmVEGKIylKaHRXP09keFIqUkUmM4I65Fa9mbif1431eGVnzGRpJoKslgUphzpGM1SQAMmKdF8YggmkplbERlhiYk2WRVNCO7yy6uk5VVdp+ree+X6TR5HAU7gFM7BhUuowx00oAkEUniGV3iznqwX6936WLSuWfnMMfyB9fkD/XKQCw==</latexit><latexit sha1_base64="AJ/s1LoL6XKHzadZBoovA/hpsRc=">AAAB+HicbVBNS8NAEJ34WetHox69LLaCIJQkUPQiFL14rGA/oA1ls920SzebsLsRaugv8eJBEa/+FG/+G7dtDtr6YODx3gwz84KEM6Ud59taW9/Y3Nou7BR39/YPSvbhUUvFqSS0SWIey06AFeVM0KZmmtNOIimOAk7bwfh25rcfqVQsFg96klA/wkPBQkawNlLfLlU8dIFqAl2jmuN4lb5ddqrOHGiVuDkpQ45G3/7qDWKSRlRowrFSXddJtJ9hqRnhdFrspYommIzxkHYNFTiiys/mh0/RmVEGKIylKaHRXP09keFIqUkUmM4I65Fa9mbif1431eGVnzGRpJoKslgUphzpGM1SQAMmKdF8YggmkplbERlhiYk2WRVNCO7yy6uk5VVdp+ree+X6TR5HAU7gFM7BhUuowx00oAkEUniGV3iznqwX6936WLSuWfnMMfyB9fkD/XKQCw==</latexit><latexit sha1_base64="AJ/s1LoL6XKHzadZBoovA/hpsRc=">AAAB+HicbVBNS8NAEJ34WetHox69LLaCIJQkUPQiFL14rGA/oA1ls920SzebsLsRaugv8eJBEa/+FG/+G7dtDtr6YODx3gwz84KEM6Ud59taW9/Y3Nou7BR39/YPSvbhUUvFqSS0SWIey06AFeVM0KZmmtNOIimOAk7bwfh25rcfqVQsFg96klA/wkPBQkawNlLfLlU8dIFqAl2jmuN4lb5ddqrOHGiVuDkpQ45G3/7qDWKSRlRowrFSXddJtJ9hqRnhdFrspYommIzxkHYNFTiiys/mh0/RmVEGKIylKaHRXP09keFIqUkUmM4I65Fa9mbif1431eGVnzGRpJoKslgUphzpGM1SQAMmKdF8YggmkplbERlhiYk2WRVNCO7yy6uk5VVdp+ree+X6TR5HAU7gFM7BhUuowx00oAkEUniGV3iznqwX6936WLSuWfnMMfyB9fkD/XKQCw==</latexit><latexit sha1_base64="AJ/s1LoL6XKHzadZBoovA/hpsRc=">AAAB+HicbVBNS8NAEJ34WetHox69LLaCIJQkUPQiFL14rGA/oA1ls920SzebsLsRaugv8eJBEa/+FG/+G7dtDtr6YODx3gwz84KEM6Ud59taW9/Y3Nou7BR39/YPSvbhUUvFqSS0SWIey06AFeVM0KZmmtNOIimOAk7bwfh25rcfqVQsFg96klA/wkPBQkawNlLfLlU8dIFqAl2jmuN4lb5ddqrOHGiVuDkpQ45G3/7qDWKSRlRowrFSXddJtJ9hqRnhdFrspYommIzxkHYNFTiiys/mh0/RmVEGKIylKaHRXP09keFIqUkUmM4I65Fa9mbif1431eGVnzGRpJoKslgUphzpGM1SQAMmKdF8YggmkplbERlhiYk2WRVNCO7yy6uk5VVdp+ree+X6TR5HAU7gFM7BhUuowx00oAkEUniGV3iznqwX6936WLSuWfnMMfyB9fkD/XKQCw==</latexit>

Page 9: Análisis de Algoritmos - UNAMgil/2020-1/_downloads/2... · Análisis de Algoritmos. ... •La solución más sencilla no siempre es la más eficiente •Los algoritmos eficientes

def f(x): ans = 0 for i in range(1000): ans += 1 print('Número de sumas hasta el momento', ans) for i in range(x): ans += 1 print('Número de sumas hasta el momento: ', ans) for i in range(x): for j in range(x): ans += 1 ans += 1

print('Número de sumas hasta el momento:', ans) return ans

1000 + x+ 2x2<latexit sha1_base64="jiGjztYDsNYvbx/uqjr4bHTy/C8=">AAAB/HicbVDLSsNAFJ34rPUV7dLNYCMIQplko8uiG5cV7APaWCbTSTt0MgkzE2kI9VfcuFDErR/izr9x2mahrQcuHM65l3vvCRLOlEbo21pb39jc2i7tlHf39g8O7aPjlopTSWiTxDyWnQArypmgTc00p51EUhwFnLaD8c3Mbz9SqVgs7nWWUD/CQ8FCRrA2Ut+uOI6LEIIXcGLKmzx4jtO3q6iG5oCrxC1IFRRo9O2v3iAmaUSFJhwr1XVRov0cS80Ip9NyL1U0wWSMh7RrqMARVX4+P34Kz4wygGEsTQkN5+rviRxHSmVRYDojrEdq2ZuJ/3ndVIdXfs5EkmoqyGJRmHKoYzhLAg6YpETzzBBMJDO3QjLCEhNt8iqbENzll1dJy6u5qObeedX6dRFHCZyAU3AOXHAJ6uAWNEATEJCBZ/AK3qwn68V6tz4WrWtWMVMBf2B9/gA2pZFA</latexit><latexit sha1_base64="jiGjztYDsNYvbx/uqjr4bHTy/C8=">AAAB/HicbVDLSsNAFJ34rPUV7dLNYCMIQplko8uiG5cV7APaWCbTSTt0MgkzE2kI9VfcuFDErR/izr9x2mahrQcuHM65l3vvCRLOlEbo21pb39jc2i7tlHf39g8O7aPjlopTSWiTxDyWnQArypmgTc00p51EUhwFnLaD8c3Mbz9SqVgs7nWWUD/CQ8FCRrA2Ut+uOI6LEIIXcGLKmzx4jtO3q6iG5oCrxC1IFRRo9O2v3iAmaUSFJhwr1XVRov0cS80Ip9NyL1U0wWSMh7RrqMARVX4+P34Kz4wygGEsTQkN5+rviRxHSmVRYDojrEdq2ZuJ/3ndVIdXfs5EkmoqyGJRmHKoYzhLAg6YpETzzBBMJDO3QjLCEhNt8iqbENzll1dJy6u5qObeedX6dRFHCZyAU3AOXHAJ6uAWNEATEJCBZ/AK3qwn68V6tz4WrWtWMVMBf2B9/gA2pZFA</latexit><latexit sha1_base64="jiGjztYDsNYvbx/uqjr4bHTy/C8=">AAAB/HicbVDLSsNAFJ34rPUV7dLNYCMIQplko8uiG5cV7APaWCbTSTt0MgkzE2kI9VfcuFDErR/izr9x2mahrQcuHM65l3vvCRLOlEbo21pb39jc2i7tlHf39g8O7aPjlopTSWiTxDyWnQArypmgTc00p51EUhwFnLaD8c3Mbz9SqVgs7nWWUD/CQ8FCRrA2Ut+uOI6LEIIXcGLKmzx4jtO3q6iG5oCrxC1IFRRo9O2v3iAmaUSFJhwr1XVRov0cS80Ip9NyL1U0wWSMh7RrqMARVX4+P34Kz4wygGEsTQkN5+rviRxHSmVRYDojrEdq2ZuJ/3ndVIdXfs5EkmoqyGJRmHKoYzhLAg6YpETzzBBMJDO3QjLCEhNt8iqbENzll1dJy6u5qObeedX6dRFHCZyAU3AOXHAJ6uAWNEATEJCBZ/AK3qwn68V6tz4WrWtWMVMBf2B9/gA2pZFA</latexit><latexit sha1_base64="jiGjztYDsNYvbx/uqjr4bHTy/C8=">AAAB/HicbVDLSsNAFJ34rPUV7dLNYCMIQplko8uiG5cV7APaWCbTSTt0MgkzE2kI9VfcuFDErR/izr9x2mahrQcuHM65l3vvCRLOlEbo21pb39jc2i7tlHf39g8O7aPjlopTSWiTxDyWnQArypmgTc00p51EUhwFnLaD8c3Mbz9SqVgs7nWWUD/CQ8FCRrA2Ut+uOI6LEIIXcGLKmzx4jtO3q6iG5oCrxC1IFRRo9O2v3iAmaUSFJhwr1XVRov0cS80Ip9NyL1U0wWSMh7RrqMARVX4+P34Kz4wygGEsTQkN5+rviRxHSmVRYDojrEdq2ZuJ/3ndVIdXfs5EkmoqyGJRmHKoYzhLAg6YpETzzBBMJDO3QjLCEhNt8iqbENzll1dJy6u5qObeedX6dRFHCZyAU3AOXHAJ6uAWNEATEJCBZ/AK3qwn68V6tz4WrWtWMVMBf2B9/gA2pZFA</latexit>

Page 10: Análisis de Algoritmos - UNAMgil/2020-1/_downloads/2... · Análisis de Algoritmos. ... •La solución más sencilla no siempre es la más eficiente •Los algoritmos eficientes

print(f(10)) Número de sumas hasta el momento: 1000 Número de sumas hasta el momento: 1010 Número de sumas hasta el momento: 1210

print(f(1000)) Número de sumas hasta el momento: 1000 Número de sumas hasta el momento: 2000 Número de sumas hasta el momento: 2002000

1000 + x+ 2x2<latexit sha1_base64="jiGjztYDsNYvbx/uqjr4bHTy/C8=">AAAB/HicbVDLSsNAFJ34rPUV7dLNYCMIQplko8uiG5cV7APaWCbTSTt0MgkzE2kI9VfcuFDErR/izr9x2mahrQcuHM65l3vvCRLOlEbo21pb39jc2i7tlHf39g8O7aPjlopTSWiTxDyWnQArypmgTc00p51EUhwFnLaD8c3Mbz9SqVgs7nWWUD/CQ8FCRrA2Ut+uOI6LEIIXcGLKmzx4jtO3q6iG5oCrxC1IFRRo9O2v3iAmaUSFJhwr1XVRov0cS80Ip9NyL1U0wWSMh7RrqMARVX4+P34Kz4wygGEsTQkN5+rviRxHSmVRYDojrEdq2ZuJ/3ndVIdXfs5EkmoqyGJRmHKoYzhLAg6YpETzzBBMJDO3QjLCEhNt8iqbENzll1dJy6u5qObeedX6dRFHCZyAU3AOXHAJ6uAWNEATEJCBZ/AK3qwn68V6tz4WrWtWMVMBf2B9/gA2pZFA</latexit><latexit sha1_base64="jiGjztYDsNYvbx/uqjr4bHTy/C8=">AAAB/HicbVDLSsNAFJ34rPUV7dLNYCMIQplko8uiG5cV7APaWCbTSTt0MgkzE2kI9VfcuFDErR/izr9x2mahrQcuHM65l3vvCRLOlEbo21pb39jc2i7tlHf39g8O7aPjlopTSWiTxDyWnQArypmgTc00p51EUhwFnLaD8c3Mbz9SqVgs7nWWUD/CQ8FCRrA2Ut+uOI6LEIIXcGLKmzx4jtO3q6iG5oCrxC1IFRRo9O2v3iAmaUSFJhwr1XVRov0cS80Ip9NyL1U0wWSMh7RrqMARVX4+P34Kz4wygGEsTQkN5+rviRxHSmVRYDojrEdq2ZuJ/3ndVIdXfs5EkmoqyGJRmHKoYzhLAg6YpETzzBBMJDO3QjLCEhNt8iqbENzll1dJy6u5qObeedX6dRFHCZyAU3AOXHAJ6uAWNEATEJCBZ/AK3qwn68V6tz4WrWtWMVMBf2B9/gA2pZFA</latexit><latexit sha1_base64="jiGjztYDsNYvbx/uqjr4bHTy/C8=">AAAB/HicbVDLSsNAFJ34rPUV7dLNYCMIQplko8uiG5cV7APaWCbTSTt0MgkzE2kI9VfcuFDErR/izr9x2mahrQcuHM65l3vvCRLOlEbo21pb39jc2i7tlHf39g8O7aPjlopTSWiTxDyWnQArypmgTc00p51EUhwFnLaD8c3Mbz9SqVgs7nWWUD/CQ8FCRrA2Ut+uOI6LEIIXcGLKmzx4jtO3q6iG5oCrxC1IFRRo9O2v3iAmaUSFJhwr1XVRov0cS80Ip9NyL1U0wWSMh7RrqMARVX4+P34Kz4wygGEsTQkN5+rviRxHSmVRYDojrEdq2ZuJ/3ndVIdXfs5EkmoqyGJRmHKoYzhLAg6YpETzzBBMJDO3QjLCEhNt8iqbENzll1dJy6u5qObeedX6dRFHCZyAU3AOXHAJ6uAWNEATEJCBZ/AK3qwn68V6tz4WrWtWMVMBf2B9/gA2pZFA</latexit><latexit sha1_base64="jiGjztYDsNYvbx/uqjr4bHTy/C8=">AAAB/HicbVDLSsNAFJ34rPUV7dLNYCMIQplko8uiG5cV7APaWCbTSTt0MgkzE2kI9VfcuFDErR/izr9x2mahrQcuHM65l3vvCRLOlEbo21pb39jc2i7tlHf39g8O7aPjlopTSWiTxDyWnQArypmgTc00p51EUhwFnLaD8c3Mbz9SqVgs7nWWUD/CQ8FCRrA2Ut+uOI6LEIIXcGLKmzx4jtO3q6iG5oCrxC1IFRRo9O2v3iAmaUSFJhwr1XVRov0cS80Ip9NyL1U0wWSMh7RrqMARVX4+P34Kz4wygGEsTQkN5+rviRxHSmVRYDojrEdq2ZuJ/3ndVIdXfs5EkmoqyGJRmHKoYzhLAg6YpETzzBBMJDO3QjLCEhNt8iqbENzll1dJy6u5qObeedX6dRFHCZyAU3AOXHAJ6uAWNEATEJCBZ/AK3qwn68V6tz4WrWtWMVMBf2B9/gA2pZFA</latexit>

Page 11: Análisis de Algoritmos - UNAMgil/2020-1/_downloads/2... · Análisis de Algoritmos. ... •La solución más sencilla no siempre es la más eficiente •Los algoritmos eficientes

• O(1)

• O(log n)

• O(n)

• O(n log n)

• O( )

• O(. )

nk<latexit sha1_base64="StWxrg+qnlgL2Kna9qOCM1xBFoU=">AAAB7nicbVA9T8MwEL2Ur1K+CowsFg0SU5V0gbGChbFI9ENqQ+W4TmvFdiLbQaqi/ggWBhBi5few8W9w2wzQ8qSTnt670929MOVMG8/7dkobm1vbO+Xdyt7+weFR9fiko5NMEdomCU9UL8SaciZp2zDDaS9VFIuQ024Y38797hNVmiXywUxTGgg8lixiBBsrdV1XPsauO6zWvLq3AFonfkFqUKA1rH4NRgnJBJWGcKx13/dSE+RYGUY4nVUGmaYpJjEe076lEguqg3xx7gxdWGWEokTZkgYt1N8TORZaT0VoOwU2E73qzcX/vH5mousgZzLNDJVkuSjKODIJmv+ORkxRYvjUEkwUs7ciMsEKE2MTqtgQ/NWX10mnUfe9un/fqDVvijjKcAbncAk+XEET7qAFbSAQwzO8wpuTOi/Ou/OxbC05xcwp/IHz+QPEUI6F</latexit><latexit sha1_base64="StWxrg+qnlgL2Kna9qOCM1xBFoU=">AAAB7nicbVA9T8MwEL2Ur1K+CowsFg0SU5V0gbGChbFI9ENqQ+W4TmvFdiLbQaqi/ggWBhBi5few8W9w2wzQ8qSTnt670929MOVMG8/7dkobm1vbO+Xdyt7+weFR9fiko5NMEdomCU9UL8SaciZp2zDDaS9VFIuQ024Y38797hNVmiXywUxTGgg8lixiBBsrdV1XPsauO6zWvLq3AFonfkFqUKA1rH4NRgnJBJWGcKx13/dSE+RYGUY4nVUGmaYpJjEe076lEguqg3xx7gxdWGWEokTZkgYt1N8TORZaT0VoOwU2E73qzcX/vH5mousgZzLNDJVkuSjKODIJmv+ORkxRYvjUEkwUs7ciMsEKE2MTqtgQ/NWX10mnUfe9un/fqDVvijjKcAbncAk+XEET7qAFbSAQwzO8wpuTOi/Ou/OxbC05xcwp/IHz+QPEUI6F</latexit><latexit sha1_base64="StWxrg+qnlgL2Kna9qOCM1xBFoU=">AAAB7nicbVA9T8MwEL2Ur1K+CowsFg0SU5V0gbGChbFI9ENqQ+W4TmvFdiLbQaqi/ggWBhBi5few8W9w2wzQ8qSTnt670929MOVMG8/7dkobm1vbO+Xdyt7+weFR9fiko5NMEdomCU9UL8SaciZp2zDDaS9VFIuQ024Y38797hNVmiXywUxTGgg8lixiBBsrdV1XPsauO6zWvLq3AFonfkFqUKA1rH4NRgnJBJWGcKx13/dSE+RYGUY4nVUGmaYpJjEe076lEguqg3xx7gxdWGWEokTZkgYt1N8TORZaT0VoOwU2E73qzcX/vH5mousgZzLNDJVkuSjKODIJmv+ORkxRYvjUEkwUs7ciMsEKE2MTqtgQ/NWX10mnUfe9un/fqDVvijjKcAbncAk+XEET7qAFbSAQwzO8wpuTOi/Ou/OxbC05xcwp/IHz+QPEUI6F</latexit><latexit sha1_base64="StWxrg+qnlgL2Kna9qOCM1xBFoU=">AAAB7nicbVA9T8MwEL2Ur1K+CowsFg0SU5V0gbGChbFI9ENqQ+W4TmvFdiLbQaqi/ggWBhBi5few8W9w2wzQ8qSTnt670929MOVMG8/7dkobm1vbO+Xdyt7+weFR9fiko5NMEdomCU9UL8SaciZp2zDDaS9VFIuQ024Y38797hNVmiXywUxTGgg8lixiBBsrdV1XPsauO6zWvLq3AFonfkFqUKA1rH4NRgnJBJWGcKx13/dSE+RYGUY4nVUGmaYpJjEe076lEguqg3xx7gxdWGWEokTZkgYt1N8TORZaT0VoOwU2E73qzcX/vH5mousgZzLNDJVkuSjKODIJmv+ORkxRYvjUEkwUs7ciMsEKE2MTqtgQ/NWX10mnUfe9un/fqDVvijjKcAbncAk+XEET7qAFbSAQwzO8wpuTOi/Ou/OxbC05xcwp/IHz+QPEUI6F</latexit>

cn<latexit sha1_base64="GI/kulU+WOeQuGqKMDOPIvnxe6w=">AAAB7nicbVA9TwJBEJ3DL8Qv1NJmI2diRe5otCTaWGIiHwmcZG8ZYMPe3mV3z4Rc+BE2Fhpj6++x89+4wBUKvmSSl/dmMjMvTATXxvO+ncLG5tb2TnG3tLd/cHhUPj5p6ThVDJssFrHqhFSj4BKbhhuBnUQhjUKB7XByO/fbT6g0j+WDmSYYRHQk+ZAzaqzUdl32KF23X654VW8Bsk78nFQgR6Nf/uoNYpZGKA0TVOuu7yUmyKgynAmclXqpxoSyCR1h11JJI9RBtjh3Ri6sMiDDWNmShizU3xMZjbSeRqHtjKgZ61VvLv7ndVMzvA4yLpPUoGTLRcNUEBOT+e9kwBUyI6aWUKa4vZWwMVWUGZtQyYbgr768Tlq1qu9V/ftapX6Tx1GEMziHS/DhCupwBw1oAoMJPMMrvDmJ8+K8Ox/L1oKTz5zCHzifP7gKjn0=</latexit><latexit sha1_base64="GI/kulU+WOeQuGqKMDOPIvnxe6w=">AAAB7nicbVA9TwJBEJ3DL8Qv1NJmI2diRe5otCTaWGIiHwmcZG8ZYMPe3mV3z4Rc+BE2Fhpj6++x89+4wBUKvmSSl/dmMjMvTATXxvO+ncLG5tb2TnG3tLd/cHhUPj5p6ThVDJssFrHqhFSj4BKbhhuBnUQhjUKB7XByO/fbT6g0j+WDmSYYRHQk+ZAzaqzUdl32KF23X654VW8Bsk78nFQgR6Nf/uoNYpZGKA0TVOuu7yUmyKgynAmclXqpxoSyCR1h11JJI9RBtjh3Ri6sMiDDWNmShizU3xMZjbSeRqHtjKgZ61VvLv7ndVMzvA4yLpPUoGTLRcNUEBOT+e9kwBUyI6aWUKa4vZWwMVWUGZtQyYbgr768Tlq1qu9V/ftapX6Tx1GEMziHS/DhCupwBw1oAoMJPMMrvDmJ8+K8Ox/L1oKTz5zCHzifP7gKjn0=</latexit><latexit sha1_base64="GI/kulU+WOeQuGqKMDOPIvnxe6w=">AAAB7nicbVA9TwJBEJ3DL8Qv1NJmI2diRe5otCTaWGIiHwmcZG8ZYMPe3mV3z4Rc+BE2Fhpj6++x89+4wBUKvmSSl/dmMjMvTATXxvO+ncLG5tb2TnG3tLd/cHhUPj5p6ThVDJssFrHqhFSj4BKbhhuBnUQhjUKB7XByO/fbT6g0j+WDmSYYRHQk+ZAzaqzUdl32KF23X654VW8Bsk78nFQgR6Nf/uoNYpZGKA0TVOuu7yUmyKgynAmclXqpxoSyCR1h11JJI9RBtjh3Ri6sMiDDWNmShizU3xMZjbSeRqHtjKgZ61VvLv7ndVMzvA4yLpPUoGTLRcNUEBOT+e9kwBUyI6aWUKa4vZWwMVWUGZtQyYbgr768Tlq1qu9V/ftapX6Tx1GEMziHS/DhCupwBw1oAoMJPMMrvDmJ8+K8Ox/L1oKTz5zCHzifP7gKjn0=</latexit><latexit sha1_base64="GI/kulU+WOeQuGqKMDOPIvnxe6w=">AAAB7nicbVA9TwJBEJ3DL8Qv1NJmI2diRe5otCTaWGIiHwmcZG8ZYMPe3mV3z4Rc+BE2Fhpj6++x89+4wBUKvmSSl/dmMjMvTATXxvO+ncLG5tb2TnG3tLd/cHhUPj5p6ThVDJssFrHqhFSj4BKbhhuBnUQhjUKB7XByO/fbT6g0j+WDmSYYRHQk+ZAzaqzUdl32KF23X654VW8Bsk78nFQgR6Nf/uoNYpZGKA0TVOuu7yUmyKgynAmclXqpxoSyCR1h11JJI9RBtjh3Ri6sMiDDWNmShizU3xMZjbSeRqHtjKgZ61VvLv7ndVMzvA4yLpPUoGTLRcNUEBOT+e9kwBUyI6aWUKa4vZWwMVWUGZtQyYbgr768Tlq1qu9V/ftapX6Tx1GEMziHS/DhCupwBw1oAoMJPMMrvDmJ8+K8Ox/L1oKTz5zCHzifP7gKjn0=</latexit>

Page 12: Análisis de Algoritmos - UNAMgil/2020-1/_downloads/2... · Análisis de Algoritmos. ... •La solución más sencilla no siempre es la más eficiente •Los algoritmos eficientes

import matplotlib matplotlib.use('TkAgg')

import matplotlib.pyplot as plt import math x=list(range(1,100)) plt.plot(x , [y * y for y in x] ) plt.plot(x, [(7 *y )* math.log(y, 2) for y in x]) plt.plot(x, [(6 *y )* math.log(y, 2) for y in x]) plt.show()