EJERCICIO 5

EJERCICIO 5

de Lourdes Alejandra Couto Burgos -
Número de respuestas: 1
Buenas, tengo una duda sobre la solucion del ejercicio 5. No logro hacer un algoritmo de orden n, y no entiendo la solucion planteada. Pueden explicarme como seria? gracias!
En respuesta a Lourdes Alejandra Couto Burgos

Re: EJERCICIO 5

de Matias Richart -

Hola.

La solución lo que hace es ir almacenando en un arreglo auxiliar llamado cantidades, la cantidad de veces que aparece cada elemento en el arreglo A (el arreglo a ordenar).

Esto lleva O(k) para inicializar cantidades y O(n) para recorrer A y contar cada elemento.

Luego, lo que hace es recorrer nuevamente A y por cada vez que aparece un elemento en cantidades lo agrega a A.

Esto es O(nk)

Veamos un ejemplo:

A = [5,1,3,2,1]

Entonces cantidades = [0,2,1,1,0,1]. Eso quiere decir que el 1 aparece 2 veces, el 2, 3 y 5 aparecen 1 vez y el 4 aparece 0 veces en A

Luego, se sobreescribe A obteniendo [1,1,2,3,4]


En cuanto a los órdenes, nos queda O(k) + O(n) + O(nk).

El mayor es O(nk) donde k es una constante que no depende de la entrada, por lo tanto es O(n).

Espero se entienda

Saludos