Definición de complejidad computacional: Conceptos y medidas

Question 1

¿Qué es la complejidad computacional?

Accepted Answer

Una medida de los recursos (tiempo y/o espacio) necesarios para resolver un problema computacional utilizando un algoritmo.

Answer

El estudio de los algoritmos eficientes

Answer

Una medida de la dificultad de un problema computacional independientemente del algoritmo

Question 2

¿Cuál de las siguientes NO es una medida común de complejidad computacional?

Accepted Answer

Velocidad de procesamiento

Answer

Tiempo de ejecución

Answer

Número de operaciones

Answer

Espacio de memoria

Question 3

¿Qué término describe un algoritmo cuya complejidad asintótica es O(1)?

Accepted Answer

Constante

Answer

Exponencial

Answer

Logarítmico

Answer

Polinómico

Question 4

¿Cuál de las siguientes afirmaciones sobre la complejidad computacional es correcta?

Accepted Answer

Puede variar según el algoritmo utilizado para resolver el problema.

Answer

Solo puede medirse para problemas de tamaño infinito.

Answer

Es una medida absoluta que no depende del algoritmo.

Question 5

¿Qué tipo de problemas se consideran generalmente computacionalmente intratables?

Accepted Answer

Problemas que tienen una complejidad asintótica exponencial o superior.

Answer

Problemas que tienen una complejidad asintótica constante.

Answer

Problemas que requieren más memoria que la disponible en cualquier computadora práctica.

Question 6

¿Qué afirmación sobre la clase de complejidad P es verdadera?

Accepted Answer

Contiene problemas que se pueden resolver en tiempo polinómico.

Answer

Contiene problemas que se pueden resolver en tiempo constante.

Answer

Contiene problemas que son inherentemente intratables.

Question 7

¿Qué tipo de reducción se utiliza para demostrar que un problema es NP-completo?

Accepted Answer

Reducción polinómica

Answer

Reducción logarítmica

Answer

Reducción lineal

Answer

Reducción exponencial

Question 8

¿Cuál de los siguientes es un enfoque común para diseñar algoritmos eficientes?

Accepted Answer

Análisis de la complejidad

Answer

Adivinanzas fundamentadas

Answer

Ensayo y error

Question 9

¿Cuál de las siguientes afirmaciones sobre el Teorema de la Jerarquía Temporal es correcta?

Accepted Answer

Para cada clase de complejidad temporal, existe una clase más difícil que no puede ser simulada por la primera en menos del doble de tiempo.

Answer

Todos los problemas en una clase de complejidad temporal se pueden resolver en tiempo polinómico.

Question 10

¿Cuál de los siguientes problemas es NP-completo?

Accepted Answer

Problema de la mochila

Answer

Búsqueda binaria

Answer

Ordenación por burbuja

Answer

Multiplicación de matrices

Question 11

¿Qué tipo de algoritmo se caracteriza por tener un tiempo de ejecución que es polinómico en el tamaño de entrada?

Accepted Answer

Algoritmo de tiempo polinómico

Answer

Algoritmo de tiempo lineal

Answer

Algoritmo de tiempo constante

Answer

Algoritmo de tiempo exponencial

Question 12

¿Qué factor no afecta a la complejidad computacional de un algoritmo?

Accepted Answer

Velocidad del procesador

Answer

Algoritmo elegido

Answer

Lenguaje de programación utilizado

Answer

Tamaño de entrada

Question 13

¿Qué clase de complejidad computacional contiene problemas que se pueden resolver en tiempo polinómico en una máquina no determinista?

Accepted Answer

NP

Answer

NP-completo

Answer

P

Answer

NP-difícil

Question 14

La complejidad computacional de un algoritmo mide:

Accepted Answer

El número de pasos elementales necesarios para resolver el problema

Answer

El tamaño del código fuente del algoritmo

Answer

La cantidad de memoria utilizada por el algoritmo

Question 15

La notación asintótica que describe el comportamiento de un algoritmo que crece linealmente con el tamaño de entrada es:

Accepted Answer

O(n)

Answer

O(log n)

Answer

O(n^2)

Answer

O(2^n)

Question 16

En complejidad computacional, la notación O(1) representa:

Accepted Answer

Un algoritmo con complejidad constante

Answer

Un algoritmo con complejidad lineal

Answer

Un algoritmo con complejidad cuadrática

Answer

Un algoritmo con complejidad exponencial

Question 17

Entre los siguientes algoritmos, el más eficiente (menor complejidad) es:

Accepted Answer

O(n^2)

Answer

O(2^n)

Answer

O(n^3)

Question 18

Un problema con complejidad computacional intratable es:

Accepted Answer

Un problema que no se puede resolver en un tiempo polinómico

Answer

Un problema que se puede resolver en tiempo constante

Answer

Un problema que se puede resolver en tiempo lineal

Question 19

¿Cuál de los siguientes problemas es NP-completo?

Accepted Answer

El problema del viajante

Answer

El problema de la multiplicación de matrices

Answer

El problema de la ordenación de enteros

Question 20

La hipótesis P = NP afirma que:

Accepted Answer

Todos los problemas NP-completos se pueden resolver en tiempo polinómico

Answer

No existen problemas intratables

Answer

Todos los problemas polinómicos son NP-completos

Question 21

El concepto que mide la eficiencia de un algoritmo en términos de consumo de memoria es:

Accepted Answer

Espacio computacional

Answer

Complejidad computacional

Answer

Tiempo de ejecución

Answer

Notación asintótica

Question 22

Un algoritmo con complejidad espacial constante es aquel que utiliza:

Accepted Answer

Una cantidad fija de memoria independientemente del tamaño de entrada

Answer

Una cantidad de memoria cuadrática con respecto al tamaño de entrada

Answer

Una cantidad de memoria lineal con respecto al tamaño de entrada

Question 23

El tiempo de ejecución de un algoritmo es una función de:

Accepted Answer

El tamaño de la entrada

Answer

El hardware utilizado

Answer

El lenguaje de programación utilizado

Answer

El sistema operativo

Question 24

¿Cuál de las siguientes expresiones representa el peor tiempo de ejecución de un algoritmo?

Accepted Answer

O(n^2)

Answer

O(n log n)

Answer

O(1)

Answer

O(log n)

Question 25

Un algoritmo con complejidad O(1) se clasifica como:

Accepted Answer

Constante

Answer

Logarítmico

Answer

Cuadrático

Answer

Exponencial

Question 26

El conjunto de todos los problemas que se pueden resolver en tiempo polinomial se conoce como:

Accepted Answer

P

Answer

NP-difícil

Answer

NP

Answer

NP-completo

Question 27

¿Cuál de las siguientes afirmaciones es verdadera sobre los problemas NP-completos?

Accepted Answer

Son difíciles de resolver y verificar

Answer

Son fáciles de resolver y verificar

Answer

Son fáciles de resolver pero difíciles de verificar

Question 28

La hipótesis P = NP implica que:

Accepted Answer

Todos los problemas NP-completos se pueden resolver en tiempo polinomial

Answer

Todos los problemas P se pueden resolver en tiempo exponencial

Answer

Todos los problemas NP-difíciles se pueden resolver en tiempo polinomial

Question 29

La notación O-grande se utiliza para describir:

Accepted Answer

El límite superior asintótico del tiempo de ejecución

Answer

El tiempo de ejecución exacto para un tamaño de entrada determinado

Answer

El límite inferior asintótico del tiempo de ejecución

Question 30

¿Qué mide la complejidad computacional?

Accepted Answer

La dificultad de un algoritmo en función del tamaño de su entrada

Answer

El tiempo que tarda un algoritmo en ejecutarse en el peor de los casos

Answer

El número máximo de instrucciones que ejecuta un algoritmo

Question 31

En la notación asintótica O(), ¿qué representa n?

Accepted Answer

El tamaño de la entrada

Answer

La memoria utilizada por el algoritmo

Answer

El número de instrucciones del algoritmo

Answer

El tiempo de ejecución del algoritmo en el peor de los casos

Question 32

Un algoritmo con una complejidad asintótica de O(1) es:

Accepted Answer

Constante

Answer

Exponencial

Answer

Lineal

Answer

Cuadrático

Question 33

¿Qué tipo de problema se considera NP-completo?

Accepted Answer

Problema de la mochila

Answer

Búsqueda binaria

Answer

Ordenamiento por inserción

Question 34

La complejidad computacional es importante porque:

Accepted Answer

Ayuda a los informáticos a predecir el rendimiento de los algoritmos

Answer

Solo es relevante para los algoritmos más complejos

Answer

Es un requisito para todos los programas informáticos

Question 35

En el contexto de la complejidad computacional, ¿qué representa la variable 'cost'?

Accepted Answer

El tiempo de ejecución o la cantidad de memoria necesaria

Answer

El tamaño de la entrada

Answer

El número de variables en el programa

Question 36

¿Qué tipo de análisis de complejidad se centra en el peor de los casos?

Accepted Answer

Análisis pesimista

Answer

Análisis promedio

Answer

Análisis amortizado

Answer

Análisis óptimo

Question 37

Un algoritmo con una complejidad asintótica de O(log n) es:

Accepted Answer

Logarítmico

Answer

Cuadrático

Answer

Lineal

Answer

Exponencial

Question 38

La complejidad computacional de un algoritmo se refiere a la cantidad de recursos que necesita para ejecutarse. ¿Qué tipo de recursos se consideran?

Accepted Answer

Tiempo y memoria.

Answer

Dificultad de comprensión.

Answer

Cantidad de código.

Answer

Número de líneas de código.

Question 39

La notación asintótica se utiliza para describir el comportamiento de un algoritmo a medida que el tamaño de entrada aumenta. ¿Qué tipo de comportamiento se describe?

Accepted Answer

Crecimiento del tiempo y la memoria.

Answer

Eficiencia de diferentes lenguajes de programación.

Answer

Complejidad del código.

Answer

Tiempo real de ejecución.

Question 40

Un algoritmo con complejidad O(n) se considera lineal. ¿Qué significa esto?

Accepted Answer

El tiempo de ejecución aumenta proporcionalmente al tamaño de entrada.

Answer

El tiempo de ejecución aumenta exponencialmente.

Answer

El tiempo de ejecución es constante.

Answer

El tiempo de ejecución es logarítmico.

Question 41

Un algoritmo con complejidad O(log n) se considera eficiente para entradas grandes. ¿Por qué?

Accepted Answer

El tiempo de ejecución aumenta lentamente a medida que el tamaño de entrada crece.

Answer

El tiempo de ejecución aumenta exponencialmente.

Answer

El tiempo de ejecución es lineal.

Answer

El tiempo de ejecución es constante.

Question 42

Un algoritmo con complejidad O(n^2) se considera:

Accepted Answer

Cuadrático.

Answer

Logarítmico.

Answer

Lineal.

Answer

Constante.

Question 43

Un algoritmo con complejidad O(2^n) se considera:

Accepted Answer

Ineficiente para entradas grandes, ya que el tiempo de ejecución crece exponencialmente.

Answer

Logarítmico.

Answer

Eficiente para entradas pequeñas.

Answer

Lineal.

Question 44

La complejidad de un algoritmo de búsqueda lineal es O(n). ¿Qué implica esto?

Accepted Answer

El algoritmo necesita revisar cada elemento de la entrada, por lo que el tiempo de ejecución aumenta linealmente con el tamaño de la entrada.

Answer

El algoritmo es logarítmico.

Answer

El algoritmo es muy rápido.

Question 45

Al analizar la complejidad de un algoritmo, ¿qué factores son importantes?

Accepted Answer

El tiempo de ejecución y la cantidad de memoria utilizada.

Answer

Solo el tiempo de ejecución.

Answer

Solo la cantidad de memoria utilizada.

Answer

La legibilidad del código.