Algoritmica

Algorítmica
Práctica 1

1. Análisis de Eficiencia de los Algoritmos
Problema 1. Dar un ejemplo de una función f(n) que esté en O(g(n)) pero no esté Ω(g(n)).
Dada una función n, n pertenece a O(n2) porque n está acotada superiormente por n2 pero no está en Ω(n2) porque al crecer n2 más rápido que n, n2 no acota inferiormente a n.
Problema 2. Un programa emplea 2s en resolver un dato detamaño 1000 de un cierto problema. ¿Cuánto tardará en resolver un dato de tamaño 3000?
a) Si el coste del algoritmo es O(n2).
Para n de 1000 -> O(10002 ) emplea un tiempo de 2 segundos. Entonces:
Para n de 3000 -> O(30002) = (30002/10002)*2sg = 18sg

b) Si el coste es O(n log2 n).
Para n de 1000 -> O(1000 * log2 1000 ) emplea un tiempo de 2 segundos. Entonces:
Para n de 3000-> O(3000 * log2 3000) =
((3000 *log2 3000)/(1000 * log2 1000))*2sg = 6,95sg

c) Si el coste es O(2n).
Para n de 1000 -> O(21000 ) emplea un tiempo de 2 segundos. Entonces:
Para n de 3000 -> O(23000 ) = ((23000 ) /(21000 ))*2= 42000 sg.
Problema 3. Justificar la siguiente igualdad entre ordenes de complejidad.
O(loga n) = O(logb n), V a, b > 1:
La solución podría ser:Olognloga= O(lognlogb) → O(f(n)) siempre es inferior a c * f(n) para c> 0
Problema 4. Justificar la siguiente relación:

Solución:

i=1nik=1k+2k+3k+4k+…+nk≥nk y 1k+2k+3k+4k+…+nk≤nk+1

Como es mayor que nk y menor que nk+1 está acotada superiormente por nk+1
Ωnk+1=1+n-1k=k0n-1k+k1n-1k+1+…=nk+…i=1nik -> Ω(nk+1)

Problema 5: Problema 5. El siguiente fragmento de código ordena las nprimeras componentes de un vector para n >= 0 por el método de inserción (Insertion Sort).
for (int i=1; i<= n; i++)
{
int p= i; int x=a[i]; boolean seguir=true;
while(p>1 && seguir)
{
if (x<a[p-1]) {a[p]=a[p-1];} else {seguir=false;}
p--;
}
a[p]=x;
}

a) Calcular manualmente el polinomio correspondiente a su tiempo de ejecución en el caso peor.

Análisis deEficiencia
Tiempos de ejecución:
– Ta: tiempo de asignación de enteros
– Tc: tiempo de comparación
– Ti: incremento de enteros
– Tv: acceso a un elemento de un vector
– Tb: tiempo de asignación de booleanos

Nº Instrucción | Ta | Tc | Ti | Tv | Tb | TOTAL |
1 | 1 | n | n-1 | - | - | Ta+(n-1)Ti+nTc |
2 | n | - | - | n | n | nTa + nTb + nTv |
3 | - | 2 | - | - | - | (n*i=0n-1i)*Tc |
4| - | 1 | - | 1 | - | (n * i=0n-1i)*max⁡(Tc+Tv,Tv+Ta,Tb) |
5 | - | - | 1 | - | - | (n*i=0n-1i)Ti |
6 | n | - | - | n | - | nTa + nTv |

Tiempo Total: O(n2)

b) Repetir el cálculo utilizando la técnica del coste asintótico.

Suponiendo el peor caso el bucle ‘for’ se ejecuta un total de n veces. Dentro del bucle ‘for’ se ejecutan 3 operaciones, con coste total O( 1 ):
int p = i; int x= a[i]; boolean seguir = true;

El bucle ‘while’ se ejecuta la primera vez 0 veces, la segunda 1 vez, la tercera 2 veces … así progresivamente, por tanto se ejecuta veces.
Dentro del bucle ‘while’ se ejecuta un ‘if’, su coste será: máx(O( 1 ), O( 1 ), O( 1 )) + O(1) = O( 1 )
Por tanto tenemos un coste total de:
T = n * O( 1 ) + n * * O( 1 ) = O(n2)

c) Todavía se puede simplificar másel estudio si hacemos uso de lo que se llama principio de la instrucción más crítica. Consiste en lo siguiente: se identifica la instrucción elemental que más veces se ejecuta. El número de veces f(n) que se ejecuta dicha instrucción es el orden de complejidad del algoritmo analizado.

La instrucción elemental que más veces se ejecuta es Ta y O(f(n)) es O(n2)

Problema 6. Expresar en forma deprograma el algoritmo de la escuela para sumar dos números de varias cifras. Suponiendo que el mayor tiene n dígitos decimales, calcular su coste asintótico.

INICIO
numero m, n
suma = 0
multiplicados = 1
llevadas = 0
mientras m ≠ 0 ó n ≠ 0 hacer
rm = resto(m,10)
m = [m/10] parte entera
rn = resto(n,10)
n = [n/10] parte entera
aux = rm + rn
si aux ≥ 10 hacer
aux = aux – 10...