Escribir un algoritmo que encuentre los k elementos más chicos de un arreglo de dimensión n, donde k ≤ n. ¿Cuál es su complejidad temporal? ¿A p...

Hay dos algoritmos principales para encontrar los k elementos más chicos de un arreglo de dimensión n:

• Ordenar el arreglo y luego tomar los primeros k elementos. Este algoritmo tiene una complejidad temporal de O(n log n).
• Utilizar un algoritmo de selección. Los algoritmos de selección tienen una complejidad temporal de O(n) en el peor de los casos, y O(n log n) en el mejor de los casos.

La complejidad temporal del primer algoritmo es mayor que la del segundo algoritmo, por lo que es ventajoso utilizar el segundo algoritmo cuando k es menor o igual a n/2.

En particular, a partir de k = n/2, la complejidad temporal del primer algoritmo es O(n log n), mientras que la complejidad temporal del segundo algoritmo es O(n log n) en el peor de los casos, y O(n) en el mejor de los casos. Por lo tanto, a partir de k = n/2, el segundo algoritmo es más eficiente que el primero.

A continuación se muestra un ejemplo de algoritmo de selección que se puede utilizar para encontrar los k elementos más chicos de un arreglo de dimensión n:

Python

def k_menores(arreglo, k):
    for i in range(k):
        for j in range(i + 1, len(arreglo)):
            if arreglo[i] > arreglo[j]:
                arreglo[i], arreglo[j] = arreglo[j], arreglo[i]
    return arreglo[:k]

Este algoritmo funciona iterando sobre los k primeros elementos del arreglo. En cada iteración, el algoritmo compara el elemento actual con el siguiente elemento. Si el elemento actual es mayor que el siguiente elemento, los dos elementos se intercambian.

Este algoritmo tiene una complejidad temporal de O(n) en el peor de los casos, y O(n) en el mejor de los casos.