• Author / Uploaded
• PERCY CONDORI YUCRA

Citation preview

UNIVERSIDAD NACIONAL DEL ALTIPLANO 7-12-2020

ANÁLISIS Y DISEÑO DE ALGORITMOS TIEMPO DE EJECUCIÓN

Percy Condori Yucra CODIGO: 191944

Ejercicios 1.- Suponga que se compara la implementación de los métodos de ordenación por inserción y merge en la misma computadora. Para la entrada de n elementos el método de inserción utiliza 8n2 pasos, miestras que por el método merge utiliza 64nlogn pasos. ¿Para qué valores de n el método por inserción vence al método merge?

n cantidad insercion mezcla 1 2 3 4 5 6 7 8 9 10 ………..

8 16 24 32 40 48 56 64 72 80 …………..

0 64 101.4376 128 148.6033981 165.4376 179.670715 192 202.8752001 212.6033981 …………..

n cantidad insercion mezcla 30 40 41 42 43 44 45 46 47 48 49 50

240 320 328 336 344 352 360 368 376 384 392 400

314.0409981 340.6033981 342.8833283 345.1083151 347.2809443 349.4036236 351.4785982 353.5079652 355.4936865 357.4376 359.34143 361.2067961

El método de inserción vence al método de merge cuando n toma valores de 2 hasta 43, a partir de 44 el método de merge vence al método de inserción. Formulas utilizadas. 8n2 (método de

inserción) y 64nlgn(método de merge)

2.Para

2.- Para cada función y cada tiempo t en la siguiente tabla, determinar el mayor tamaño n de número de elementos que puede ser resuelto en el tiempo t indicado. Suponga que el algoritmo demora f(n) microsegundos. 1 SECOND 𝑙𝑔𝑛

6

1 MINUTE 7

1 HOUR 8

1 DAY

1 MONTH 8

9

1 YEAR

1 CENTURY 10

12

√𝜂

210 1012

26∗10 36 ∗ 1014

236∗10 1296 ∗ 1016

2864∗10 7464 ∗ 1016

22592∗10 6718464∗ 1018

294608∗10 8950673664 ∗ 1020

2946008∗10 8950673664*1024

𝑛 𝑛 𝑙𝑔 𝑛 𝑛2 𝑛3

106 62746 103 102

6*107 2801417 24494897 391

36*108 …………. 6 ∗ 104 1532

864*108 …………. 293938 4420

2592*109 …………. 1609968 13736

94608*1010 …………. 30758413 98169

946008*1012 …………. 307584134 455661

2𝑛 𝑛!

19 9

25 11

31 12

36 13

41 15

49 17

56 18

Las operaciones son realizadas en los siguientes enlaces que generan un software que calcula conversión de tiempos de 1segundo a minutos, a horas, a días, ect. Ejemplo: 1 segundo es igual a 106 microsegundos. 1 minuto es igual a 6*107 microsegundos así sucesivamente las equivalencias de los tiempos. http://www.whatsabyte.com/P1/byteconverter.htm http://www.advancedconverter.com/es/conversion-de-unidades/convertir-tiempo/segundos-a-horas