Taller de análisis de algoritmos
JoseVilladaExamen15 de Agosto de 2020
3.988 Palabras (16 Páginas)158 Visitas
Taller de análisis de algoritmos
- Un algoritmo de complejidad O(n2) tarda 15 segundos en realizar un determinado procesamiento sobre un ordenador a 450 MHz. ¿Cuánto tiempo se tarda en realizar el mismo procesamiento con el mismo algoritmo en un procesamiento con el mismo algoritmo en una máquina 3 veces más lenta? ¿Si en esta misma máquina cambiamos el tamaño del problema al doble, cuánto se va a tardar?
- Sea (𝑛) = 4𝑛2 − 3𝑛 + 2 el tiempo de ejecución de un algoritmo. Demostrar si es cierta o falsa cada una de las siguientes afirmaciones. Explicar por qué en cada caso:
- 𝑇(𝑛) ∉ 𝑂(𝑛2 log(𝑛))
- 𝑇(𝑛) ∉ 𝑂(𝑛3)
- 𝑇(𝑛) ∈ 𝑂(𝑛𝑙𝑜𝑔(𝑛))
- 𝑇(𝑛) ∈ 𝑂(𝑛2)
- ¿Cuáles de las siguientes respuestas son verdaderas y cuáles falsas? Explicar cada respuesta.
- 𝑛2 ∈ 𝑂(𝑛3)
- 𝑛3 ∈ 𝑂(𝑛3)
- 4𝑛3 − 3𝑛 + 2 ∈ 𝑂(𝑛𝑙𝑜𝑔(𝑛))
- 𝑛 ∈ 𝑂(𝑛3)
- Hallar la complejidad para el siguiente algoritmo. Explique la respuesta de acuerdo con las reglas vistas en clase.
- para i desde 1 hasta n hacer
- para j desde n hasta i + 1 dec -1 hacer
- si a[j − 1] > a[j] entonces
- temp = a[j − 1];
- a[j − 1] = a[j];
- a[j] = temp
- fsi
- fpara
- fpara
- Hallar la complejidad para el siguiente algoritmo. Explique la respuesta de acuerdo con las reglas vistas en clase.
maximoArray(A)->máximo Entrada A array de n enteros
Salida elemento máximo de A
INICIO
maxActual<-A[0]
PARA i <- 1 HASTA n - 1 HACER
SI A[i] > maxActual
ENTONCES maxActual <- A[i]
DEVOLVER maxActual
FIN
- Explicar cuál es la complejidad de un algoritmo cuyo tiempo de ejecución es (𝑛) = 5𝑛3 + 3𝑛2 + 1 ¿La complejidad podría ser O(n4)? ¿Por qué?
- Hallar la complejidad para el siguiente algoritmo. Explique la respuesta de acuerdo con las reglas vistas en clase.
mediasPrefijas1(vector,n) -> vector
INICIO
A <- nuevo Array de n enteros
i <- 0
MIENTRAS (i < n)
s <- X[0] j <- 1
MIENTRAS (j <= i) s <- s + X[j] j <- j + 1 FIN-MIENTRAS
A[i] <- s / (i + 1) i <- i + 1
FIN-MIENTRAS
DEVOLVER A
FIN
- Hallar la complejidad para el siguiente algoritmo. Explique la respuesta de acuerdo con las reglas vistas en clase.
INICIO
i <- 1 MIENTRAS (i < n)
x <- T[i] j <- i - 1
MIENTRAS (j > 0 Y T[j] > x)
T[j+1] <- T[j] j <- j - 1 FIN-MIENTRAS
T[j+1] <- x
i <- i + 1
FIN-MIENTRAS
FIN
- Hallar la complejidad para el siguiente algoritmo. Explique la respuesta de acuerdo con las reglas vistas en clase.
for i:= 1 to N for j:= 1 to N suma:= 0 for k:= 1 to N
suma:=suma+a[i,k]*a[k,j]
end c[i, j]:= suma
end end
- Hallar la complejidad para el siguiente algoritmo. Explique la respuesta de acuerdo con las reglas vistas en clase.
A[0, (n-1) div 2]:= 1
key:= 2 i:= 0 j:= (n-1) div 2
cuadrado:= n*n
while key<=cuadrado do k:= (i-1) mod n l:= (j-1) mod n if A[k, l] = 0 then i:= (i + 1) mod n else i:= k
j:= l
end A[i, j]:= key key:= key+1 end
- Hallar la complejidad para el siguiente algoritmo. Explique la respuesta de acuerdo con las reglas vistas en clase.
for i:= 1 to N do if Impar(i) then for j:= i to n do x:= x + 1 else for j:= 1 to i do y:= y + 1 end end end
- Hallar la complejidad para el siguiente algoritmo. Explique la respuesta de acuerdo con las reglas vistas en clase
i:= 1
mientras i ≤ n hacer
si a[i] ≥ a[n] entonces
a[n]:=a[i] finsi i:= i *2
finmientras
- Hallar la complejidad para el siguiente algoritmo. Explique la respuesta de acuerdo con las reglas vistas en clase
cont:=0 para i:= 1,...,n hacer
para j:= 1,...,i-1 hacer
si a[i] < a[j] entonces
cont:= cont + 1
finsi
...