Analisis de algoritmos

TAREA No 2 ANALISIS DE ALGORITMOS

1. Considere el problema de ordenar n números guardados en un arreglo A primero encontrando el elemento más pequeño de A y colocarlo en la primera entrada deotro arreglo B. Después encontrar el segundo elemento más pequeño en A y colocarlo en la segunda entrada de B. Continuar de esta forma para los n elementos de A. Escriba el pseudocódigo para estealgoritmo, que se conoce ordenación por selección. De los tiempos de corrida para el mejor caso y el peor caso en la notación.
Operaciones Costo
para i=1 hasta n-1 n-1 c1
min = i; n-1 c2para j=i+1 hasta n (n-1)(n-1) c3
si A[j] < A[min] entonces j=i+1ntj c4
min = j j=i+1n(tj-1) c5
fin si
fin para
B[i]=A[min] n-1 c6A[min]=A[i] n-1 c7
fin para
B[n]=A[n] 1 c8

Mejor Caso.
T(n) = (c1+c2+c6+c7)(n-1)+c3(n-1)(n-1)

2. Considere el problema de evaluar un polinomio en un punto. Dados n coeficientesa0, a1, ... ,an-1 y un número real x, se desea calcular a0 + a1 x1+ … +an-1xn-1. Describa un algoritmo de cálculo directo para este problema y encuentre su tiempo de ejecución en notación. Describaun algoritmo de tiempo (n) que use el siguiente método (llamado regla de Horner) para rescribir el polinomio
a0 + a1 x1+ … +an-1xn-1 = (… (an-1x + an-2 ) x + … + a1)x + a0 .

3. Dada unasucesión de n números 0 y 1 en el arreglo A[1..n], se desea organizarlos de manera que los números 0 queden agrupados a la izquierda y los números 1 a la derecha. La operación básica es comparar dosdígitos adyacentes e intercambiar sus posiciones, si se quiere. Diseñe un algoritmo y reporte el pseudocódigo. Haga un análisis del peor tiempo de corrida para este algoritmo.

4. Suponga que tiene unarreglo A[1..n] con n números y llama al algoritmo Algo-1(A,r). Diga que hace este algoritmo y haga un análisis del peor tiempo de corrida para este algoritmo.
Algo-1(A,r) Algo-2(A,r)
1 if...