Universidad Michoacana de San Nicolás de Hidalgo Facultad de Ingeniería Eléctrica Estructuras de Datos
Ramírez Rueda Juventino Ing. en Computación 0686696C
Mostrar por inducción que ?? ?? =????1 + ??????2 es válida para cualquier N con ?? = 2?? . Considerando que el número de elementos es potencia de 2 N = 32 = 2 . Definimos C1 como el tiempo para ordenar un arreglo o lista de tamaño unitario y C2el tiempo para pegar un elemento. Así el tiempo para ordenar N elementos lo resolvemos con la recurrencia ?? ?? = 2 ?? Caso base ?? = 1 ?? ???? = ?? ?? ?? 21 = 2 ?? ?? 2 = 2 ??
2 2 ???? ?? 21 2
5?? + ????2 2
+ ???? ???? + 21 ??2
+ 2??2
?? 2 = 2 ?? 1 + 2??2 Como ?? 1 = ??1 ?? 2 = 2 ??1 + 2??2 ?? ???? = ???? ???? + ?????? ???? ?? 21 = 21 ??1 + 1 21 ??2 ?? 2 = 2??1 + 2??2 Para el casobase ambas expresiones son iguales Paso recursivo ?? 2??+1 = 2 ??
2 ??+1 2
+ 2??+1 ??2
?? 2??+1 = 2 ?? 2?? + 2??+1 ??2 ?? 2??+1 = 2??+1 ??1 + ?? + 1 2??+1 ??2 ?? 2??+1 = 2??+1 ??1 + ?? + 12??+1 ??2 ?? 2??+1 = 2 2?? ??1 + ??2?? ??2 + 2??+1 ??2 ?? 2??+1 = 2 ?? 2?? + 2?? +1 ??2 Asi queda demostrado que ?? ?? = ????1 + ??????2 es válida para cualquier N.
1
Universidad Michoacana de SanNicolás de Hidalgo Facultad de Ingeniería Eléctrica Estructuras de Datos
Ramírez Rueda Juventino Ing. en Computación 0686696C
Hacer la simulación para ordenar el arreglo A = {5, 7, 0, 3, 10, 20, 1,15} utilizando: a) Burbuja b) Selection Sort c) MergeSort
Burbuja A = {5, 7, 0, 3, 10, 20, 1, 15} A = {5, 7, 0, 3, 10, 1, 20, 15} A = {5, 7, 0, 3, 10, 1, 15, 20} A = {5, 7, 0, 3, 10, 1, 15, 20} A ={5, 7, 0, 3, 1, 10, 15, 20} A = {5, 7, 0, 3, 1, 10, 15, 20} A = {5, 0, 7, 3, 1, 10, 15, 20} A = {5, 0, 3, 7, 1, 10, 15, 20} A = {5, 0, 3, 1, 7, 10, 15, 20} A = {5, 0, 3, 1, 7, 10, 15, 20} A = {0, 5,3, 1, 7, 10, 15, 20} A = {0, 3, 5, 1, 7, 10, 15, 20} A = {0, 3, 1, 5, 7, 10, 15, 20} A = {0, 3, 1, 5, 7, 10, 15, 20} A = {0, 1, 3, 5, 7, 10, 15, 20} A = {0, 1, 3, 5, 7, 10, 15, 20}…
