Análisis de Algoritmos: Optimización y Evaluación del Rendimiento

Question 1

¿Qué implica que un algoritmo tenga una complejidad temporal lineal?

Accepted Answer

Su tiempo de ejecución crece proporcionalmente al tamaño de la entrada.

Answer

Su tiempo de ejecución es constante.

Answer

Su tiempo de ejecución es exponencial.

Question 2

¿Qué método se utiliza para comparar la eficiencia de dos algoritmos?

Accepted Answer

Análisis asintótico

Answer

Perfilado

Answer

Simulación

Answer

Experimentación empírica

Question 3

Un algoritmo tiene un espacio de memoria de O(log n). ¿Qué significa esto?

Accepted Answer

La cantidad de memoria utilizada crece logarítmicamente con el tamaño de la entrada.

Answer

La cantidad de memoria utilizada es constante.

Answer

La cantidad de memoria utilizada es lineal.

Question 4

Un algoritmo es Ω(n^2). ¿Qué implica esto sobre su eficiencia?

Accepted Answer

Tiene una baja eficiencia para entradas grandes.

Answer

Tiene una eficiencia lineal.

Answer

Tiene una eficiencia constante.

Answer

Tiene una alta eficiencia para entradas pequeñas.

Question 5

¿Qué técnica de análisis se utiliza para determinar el peor caso de rendimiento de un algoritmo?

Accepted Answer

Análisis de casos límite

Answer

Análisis de casos promedio

Answer

Análisis probabilístico

Answer

Análisis de casos óptimos

Question 6

Un algoritmo tiene una complejidad temporal de Θ(n log n). ¿Qué significa esto?

Accepted Answer

Su tiempo de ejecución crece proporcionalmente a n log n.

Answer

Su tiempo de ejecución es constante.

Answer

Su tiempo de ejecución es lineal.

Question 7

Indique cuál de las siguientes notaciones asintóticas representa el peor caso de un algoritmo con complejidad temporal O(n^2) + O(n log n).

Accepted Answer

O(n^2)

Answer

O(n log^2 n)

Answer

O(n log n)

Answer

O(n^2 log n)

Question 8

Un algoritmo tiene un tiempo de ejecución de f(n) = 0,5n^3 - 2n^2 + 3n. ¿Cuál es su orden asintótico?

Accepted Answer

O(n^3)

Answer

O(1)

Answer

O(n)

Answer

O(n^2)

Question 9

¿Qué técnica de análisis de algoritmos se emplea para determinar una cota superior del tiempo de ejecución de un algoritmo?

Accepted Answer

Análisis del peor caso

Answer

Análisis del mejor caso

Answer

Análisis del caso promedio

Answer

Análisis amortizado

Question 10

Un algoritmo iterativo contiene bucles for anidados con complejidades O(n) y O(log n), respectivamente. ¿Cuál es su complejidad temporal?

Accepted Answer

O(n log n)

Answer

O(log n)

Answer

O(n)

Answer

O(n^2)

Question 11

¿Cuál de las siguientes afirmaciones sobre el análisis de algoritmos es correcta?

Accepted Answer

El análisis de algoritmos proporciona estimaciones del tiempo de ejecución y del espacio de memoria, no valores exactos.

Answer

El análisis de algoritmos puede predecir con precisión el tiempo de ejecución de cualquier algoritmo.

Question 12

Un algoritmo recursivo presenta una relación de recurrencia T(n) = 2T(n/2) + n. Utilizando el método maestro, ¿cuál es su orden asintótico?

Accepted Answer

O(n log n)

Answer

O(2^n)

Answer

O(n)

Answer

O(n^2)

Question 13

¿Qué beneficio aporta el análisis de la complejidad espacial de los algoritmos?

Accepted Answer

Optimizar el uso de memoria para evitar problemas de desbordamiento.

Answer

Mejorar la legibilidad del código fuente.

Answer

Predecir el tiempo de ejecución del algoritmo.

Question 14

¿Qué técnica de análisis de algoritmos ofrece la mayor precisión?

Accepted Answer

Análisis empírico

Answer

Análisis del caso promedio

Answer

Análisis asintótico

Answer

Análisis del peor caso

Question 15

Un algoritmo de ordenación tiene complejidad temporal O(n^2). ¿Qué afirmación sobre este algoritmo es cierta?

Accepted Answer

Su tiempo de ejecución es cuadrático, es decir, crece proporcionalmente al cuadrado del tamaño de la entrada.

Answer

Su tiempo de ejecución es lineal, es decir, crece proporcionalmente al tamaño de la entrada.

Question 16

¿Qué notación asintótica representa el menor tiempo de ejecución posible de un algoritmo que procesa n elementos?

Accepted Answer

O(1)

Answer

O(log n)

Answer

O(n^2)

Answer

O(n)

Question 17

Un algoritmo tiene un tiempo de ejecución de 5n^3 + 2n^2 + 10n. ¿Cuál es su notación asintótica?

Accepted Answer

O(n^3)

Answer

O(1)

Answer

O(n)

Answer

O(n^2)

Question 18

Un algoritmo utiliza 50 bytes para almacenar cada elemento de un conjunto de datos. Si el tamaño del conjunto de datos es n, ¿cuál es la notación asintótica del espacio de memoria utilizado?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(log n)

Answer

O(n^2)

Question 19

El algoritmo de ordenación por inserción tiene un tiempo de ejecución asintótico de:

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(n log n)

Answer

O(1)

Question 20

Un algoritmo tiene un tiempo de ejecución de 50n^2 para n valores de entrada. Si se triplica el tamaño de la entrada, ¿cuál será su nuevo tiempo de ejecución asintótico?

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(1)

Answer

O(log n)

Question 21

Un algoritmo tiene un espacio de memoria de 200n^2 + 100n. ¿Cuál es su notación asintótica para el espacio de memoria?

Accepted Answer

O(n^2)

Answer

O(log n)

Answer

O(n)

Answer

O(1)

Question 22

¿Cuál de las siguientes notaciones asintóticas representa el peor caso asintótico de un algoritmo?

Accepted Answer

O(n^2)

Answer

O(log n)

Answer

O(n)

Answer

O(1)

Question 23

Un algoritmo tiene un tiempo de ejecución de 3n^2 + 2n + 1 operaciones. ¿Cuál es su complejidad temporal asintótica?

Accepted Answer

O(n^2)

Answer

O(n^3)

Answer

O(1)

Answer

O(n)

Question 24

El análisis de algoritmos es esencial porque permite predecir:

Accepted Answer

El rendimiento de un algoritmo antes de implementarlo.

Answer

Los errores que puede contener un algoritmo.

Answer

El coste de implementación de un algoritmo.

Question 25

¿Qué tipo de recurrencia representa la siguiente función de recurrencia: T(n) = T(n-1) + 1?

Accepted Answer

Recurrencia lineal de primer orden

Answer

Recurrencia recursiva

Answer

Recurrencia no lineal

Answer

Recurrencia maestra

Question 26

El teorema maestro se utiliza para resolver recurrencias de la forma:

Accepted Answer

T(n) = aT(n/b) + f(n)

Answer

T(n) = T(n-1) + f(n)

Answer

T(n) = T(n/2) + T(n/4)

Answer

T(n) = 2T(n/2) + n

Question 27

¿Cuál de las siguientes herramientas de análisis de algoritmos proporciona información detallada sobre el rendimiento de un algoritmo?

Accepted Answer

Perfil de ejecución

Answer

Análisis estático

Answer

Análisis de errores

Answer

Debug

Question 28

¿Qué notación asintótica representa el peor comportamiento asintótico en el peor de los casos?

Accepted Answer

Ω(n^2)

Answer

O(1)

Answer

Θ(n)

Answer

O(n log n)

Question 29

Un algoritmo tiene un tiempo de ejecución O(n) y un espacio de memoria Θ(n^2). ¿Qué complejidad tiene el algoritmo?

Accepted Answer

Tiempo O(n), Espacio Θ(n^2)

Answer

Tiempo O(n^2), Espacio O(n)

Answer

Tiempo Θ(n^2), Espacio O(n)

Answer

Tiempo Θ(n), Espacio O(n^2)

Question 30

¿Qué técnica de diseño de algoritmos se utiliza para dividir un problema en subproblemas más pequeños?

Accepted Answer

Dividir y conquistar

Answer

Retroceso

Answer

Búsqueda por anchura

Answer

Programación dinámica

Question 31

¿Qué algoritmo se utiliza para encontrar el camino más corto entre dos vértices en un grafo ponderado?

Accepted Answer

Algoritmo de Dijkstra

Answer

Algoritmo de Kruskal

Answer

Algoritmo de Floyd-Warshall

Question 32

¿Cuál es el orden de complejidad temporal de peor caso para el algoritmo de ordenación por burbuja?

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(1)

Answer

O(n log n)

Question 33

Un algoritmo tiene una complejidad temporal de O(2^n). ¿Cómo se clasifica su eficiencia?

Accepted Answer

Exponencial

Answer

Polinómica

Answer

Lineal

Question 34

Un algoritmo de búsqueda tiene un tiempo de ejecución promedio de O(log n). ¿Cuál es la altura máxima del árbol de búsqueda?

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(1)

Answer

O(n^2)

Question 35

Un algoritmo tiene un tiempo de ejecución de T(n) = 3n^2 + 2n + 1. ¿Cuál es su complejidad asintótica?

Accepted Answer

O(n^2)

Answer

O(n log n)

Answer

O(n)

Answer

O(2^n)

Question 36

Un algoritmo de ordenamiento utiliza un algoritmo de partición y un algoritmo de ordenamiento recursivo sobre cada subarreglo. ¿Cuál es la complejidad asintótica esperada del algoritmo de ordenamiento?

Accepted Answer

O(n log n)

Answer

O(n)

Answer

O(n^2)

Answer

O(2^n)

Question 37

Un algoritmo utiliza una tabla hash con m ranuras para almacenar n elementos. La función hash utilizada distribuye uniformemente los elementos en las ranuras. ¿Cuál es la complejidad asintótica esperada para insertar un elemento en la tabla hash?

Accepted Answer

O(1)

Answer

O(n^2)

Answer

O(log n)

Answer

O(n)

Question 38

Se tiene un algoritmo de búsqueda de un elemento en un arreglo ordenado. El algoritmo utiliza la búsqueda binaria. ¿Cuál es la complejidad asintótica en el peor de los casos para encontrar el elemento?

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(1)

Question 39

Un algoritmo calcula el producto de dos matrices de tamaño n x n. ¿Cuál es la complejidad asintótica del algoritmo?

Accepted Answer

O(n^3)

Answer

O(n log n)

Answer

O(n)

Answer

O(n^2)

Question 40

Un algoritmo de búsqueda de un elemento en un grafo utiliza la búsqueda en amplitud. ¿Cuál es la complejidad asintótica en el peor de los casos para encontrar el elemento en un grafo con n vértices y m aristas?

Accepted Answer

O(n + m)

Answer

O(n)

Answer

O(m)

Answer

O(n^2)