Taller de análisis de algoritmos

Taller de análisis de algoritmos

1. 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?

1. 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:

1. 𝑇(𝑛) ∉ 𝑂(𝑛2 log(𝑛))
2. 𝑇(𝑛) ∉ 𝑂(𝑛3)
3. 𝑇(𝑛) ∈ 𝑂(𝑛𝑙𝑜𝑔(𝑛))
4. 𝑇(𝑛) ∈ 𝑂(𝑛2)

1. ¿Cuáles de las siguientes respuestas son verdaderas y cuáles falsas? Explicar cada respuesta.

1. 𝑛2 ∈ 𝑂(𝑛3)
2. 𝑛3 ∈ 𝑂(𝑛3)
3. 4𝑛3 − 3𝑛 + 2 ∈ 𝑂(𝑛𝑙𝑜𝑔(𝑛))
4. 𝑛 ∈ 𝑂(𝑛3)

1. Hallar la complejidad para el siguiente algoritmo. Explique la respuesta de acuerdo con las reglas vistas en clase.

1. para i desde 1 hasta n hacer
2. para j desde n hasta i + 1 dec -1 hacer
3. si a[j − 1] > a[j] entonces
4. temp = a[j − 1];
5. a[j − 1] = a[j];
6. a[j] = temp
7. fsi
8. fpara
9. fpara

1. 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

1. 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é?

1. 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          

1. 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                    

...