Test cuestionario sobre notación Big O - the question form
Preguntas: 16 · 10 minutos
1. Una búsqueda binaria recursiva pasa únicamente índices del arreglo y crea una llamada recursiva en cada nivel. ¿Cuál es la complejidad del espacio auxiliar de la pila de llamadas?
O(n), porque el arreglo original contiene n elementos.
O(1), porque cada marco de pila individual tiene tamaño constante.
O(log n), porque se agrega un marco en cada nivel mientras el rango de búsqueda se reduce repetidamente a la mitad.
O(n log n), porque el tamaño del arreglo se combina con la profundidad de la recursión.
2. Un algoritmo realiza 4n² + 3n + 20 operaciones básicas. ¿Cuál es su tiempo de ejecución asintótico ajustado?
Tiempo cuadrático, porque el término n² domina a medida que n crece.
Tiempo lineal, porque se eliminan los términos de orden inferior y las constantes.
Tiempo logarítmico, porque solo importa la cantidad de dígitos del tamaño de la entrada.
Tiempo cúbico, porque la expresión contiene tres términos distintos.
3. Si un algoritmo tarda Θ(n²), aproximadamente ¿cómo cambia su cantidad de trabajo cuando n se duplica para valores grandes de n?
Se vuelve aproximadamente cuatro veces mayor.
Se vuelve aproximadamente dos veces mayor.
Se vuelve aproximadamente ocho veces mayor.
Permanece aproximadamente igual.
4. Un bucle externo se ejecuta con i desde 1 hasta n. Para cada i, un bucle interno se ejecuta i veces. ¿Cuál es la complejidad temporal total ajustada?
Tiempo cuadrático, porque 1 + 2 + ... + n crece proporcionalmente a n².
Tiempo lineal, porque el bucle externo tiene exactamente n iteraciones.
Tiempo lineal-logarítmico, porque las longitudes del bucle interno varían entre 1 y n.
Tiempo logarítmico, porque cada iteración sucesiva cambia el límite del bucle.
5. Con una representación mediante listas de adyacencia, la búsqueda en anchura visita cada vértice alcanzable y examina cada arista relevante una cantidad acotada de veces. En términos de vértices V y aristas E, ¿cuál es su complejidad temporal?
O(log V), porque el recorrido divide repetidamente el conjunto de vértices.
O(V) para todo grafo, independientemente de cuántas aristas contenga.
O(V + E), teniendo en cuenta tanto los vértices visitados como las aristas examinadas.
O(VE), porque cada vértice requiere recorrer todas las aristas.
6. Una variable comienza en 1 y se duplica después de cada iteración hasta alcanzar o superar n. ¿Cuántas iteraciones se realizan asintóticamente?
O(log n) iteraciones.
O(n) iteraciones.
O(1) iteraciones.
O(n log n) iteraciones.
7. Un algoritmo de divide y vencerás divide un problema en dos subproblemas de la mitad del tamaño y realiza trabajo adicional lineal en cada nivel. Su relación de recurrencia es T(n) = 2T(n/2) + Θ(n). ¿Cuál es la solución ajustada?
Tiempo total logarítmico, contando solo el número de niveles recursivos.
Tiempo total lineal, suponiendo que todo el trabajo de la recursión se realiza una sola vez.
Tiempo total cuadrático, al multiplicar los dos subproblemas por el tamaño de la entrada.
Tiempo total lineal-logarítmico, porque cada uno de los niveles, cuya cantidad es logarítmica, realiza una cantidad total de trabajo lineal.
8. ¿Qué significa con mayor precisión un tiempo O(1)?
La operación siempre requiere exactamente una instrucción de máquina.
Se garantiza que la operación es más rápida que cualquier operación O(log n).
La operación utiliza una unidad de memoria por cada elemento de entrada.
Su tiempo de ejecución está acotado independientemente del tamaño de la entrada.
9. Una tabla hash utiliza encadenamiento separado y las n claves almacenadas colisionan en el mismo depósito. ¿Cuál es el tiempo de búsqueda en el peor caso en esta situación?
O(1), porque la búsqueda en una tabla hash siempre toma tiempo constante.
O(log n), porque el tamaño del depósito se reduce repetidamente a la mitad.
O(n log n), porque el hashing y el recorrido de la cadena se multiplican.
O(n), porque la búsqueda podría recorrer toda la cadena.
10. ¿Qué notación establece que g(n) es tanto una cota superior asintótica como una cota inferior asintótica de f(n)?
Big O, que por sí sola expresa una cota superior asintótica.
Big Theta, que expresa cotas asintóticas superior e inferior coincidentes.
Big Omega, que por sí sola expresa una cota inferior asintótica.
o minúscula, que expresa una tasa de crecimiento asintótico estrictamente menor.
11. ¿Cómo se compara Θ(n log n) con Θ(n²) cuando n se vuelve suficientemente grande?
Θ(n log n) termina creciendo más rápido porque contiene dos factores.
Su orden asintótico depende de la base del logaritmo.
Tienen la misma tasa de crecimiento asintótico.
Θ(n log n) termina creciendo más lentamente que Θ(n²).
12. ¿Qué afirma f(n) = O(g(n)) sobre el crecimiento de f(n)?
A partir de cierto tamaño de entrada, f(n) se mantiene igual o por encima de un múltiplo constante positivo de g(n).
A partir de cierto tamaño de entrada, f(n) se mantiene igual o por debajo de un múltiplo constante positivo de g(n).
Para todo tamaño de entrada, f(n) y g(n) deben tener valores exactamente iguales.
A medida que crece la entrada, la razón entre f(n) y g(n) debe tender a cero.
13. Un algoritmo recorre una vez un arreglo, realiza trabajo constante sobre cada elemento y debe inspeccionar todos los elementos. ¿Cuál es su tiempo de ejecución ajustado?
Tiempo constante, porque la operación realizada sobre cada elemento es constante.
Tiempo lineal, porque la cantidad de trabajo crece en proporción directa a la longitud del arreglo.
Tiempo logarítmico, porque se puede acceder a los elementos del arreglo mediante su índice.
Tiempo cuadrático, porque la inspección y el procesamiento son dos acciones distintas.
14. Un bucle procesa los n elementos y, cuando termina, un segundo bucle procesa de forma independiente los n elementos. Ambos realizan trabajo constante por elemento. ¿Cuál es la complejidad combinada?
O(n²), porque hay dos bucles.
O(log n), porque el trabajo se divide entre los bucles.
O(n), porque se suman los costos de los dos bucles lineales.
O(1), porque cada iteración realiza trabajo constante.
15. Una búsqueda binaria descarta repetidamente la mitad de un arreglo ordenado. ¿Cuál es su complejidad temporal en el peor caso?
Tiempo lineal-logarítmico, porque cada comparación se combina con un recorrido completo.
Tiempo lineal, porque podría ser necesario revisar cada elemento del arreglo.
Tiempo logarítmico, porque el intervalo de búsqueda restante se reduce a la mitad en cada paso.
Tiempo cuadrático, porque se controlan dos límites del arreglo.
16. Un programa tiene un bucle externo que se ejecuta n veces. En cada iteración externa, un bucle interno también se ejecuta n veces y realiza trabajo constante. ¿Cuál es la complejidad temporal total?
Tiempo constante, porque el trabajo dentro del bucle interno es constante.
Tiempo cuadrático, porque se realizan n iteraciones internas en cada una de las n iteraciones externas.
Tiempo lineal, porque ambos bucles utilizan el mismo tamaño de entrada.
Tiempo logarítmico, porque los bucles anidados reducen la entrada restante.