Complejidad (tema 2)

¿Cuál es el objetivo de la etapa de análisis en el Diseño y Análisis de un Algoritmo?. Determinar el lenguaje y herramientas disponibles para su desarrollo. Estimar los recursos que consumirá el algoritmo una vez implementado. Estimar la potencia y características del equipo informático necesarios para el correcto funcionamiento del algoritmo.

¿Cuál de las siguientes jerarquías de complejidades es la correcta?. O(1)⊂O(lg n)⊂O(lg lg n) ⊂ ... ... ⊂ (n!)⊂O(2^n) ⊂O(n^n). ... ⊂ (2^n)⊂O(n!) ⊂O(n^n).

¿Cuál de los siguientes algoritmos de ordenación tiene menor complejidad?. Burbuja. Inserción directa. Mergesort.

¿El tiempo de ejecución de un algoritmo depende de la talla del problema?. Sí, siempre. No, nunca. No necesariamente.

Ordena de menor a mayor las siguientes complejidades: 3,1,2 y 4. 1,3,2 y 4. 1,3,4 y 2.

El estudio de la complejidad resulta realmente interesante para tamaños grandes de problema por varios motivos: Las diferencias reales en tiempo de compilación de algoritmos con diferente coste para tamaños pequeños del problema no suelen ser muy significativas. Las diferencias reales en tiempo de ejecución de algoritmos con diferente coste para tamaños grandes del problema no suelen ser muy significativas. Ninguna de las anteriores.

¿Por que se emplean funciones de coste para expresar el coste de una algoritmo?. Para poder expresar el coste de los algoritmos con mayor exactitud. Para que la expresión del coste del algoritmo sea válida para cualquier entrada al mismo. Para poder expresar el coste de un algoritmo mediante una expresión matemática.

El caso base de una ecuación de recurrencia asociada a la complejidad temporal de un algoritmo expresa: El coste de dicho algoritmo en el mejor de los casos. El coste de dicho algoritmo en el peor de los casos. Ninguna de las anteriores.

La complejidad de la función TB es: Θ ( n ). Θ (n · lg n). Θ (n^2 · lg n).

Dado el polinomio f(n)= A(m) n^m + A(m-1) n^(m-1) + … + A0, con A(m) ∈ R+ entonces f pertenece al orden: O(n^m). Ω(n^m). La dos respuestas anteriores son correctas.

Si f1(n) ∈ Ο(g1(n)) y f2(n) ∈ Ο(g2(n)) entonces: f1(n)·f2(n) ∈ Ο(maximo(g1(n),g2(n))). f1(n)·f2(n) ∈ Ο (g1(n)· g2(n)). Ambas son correctas.

Si f1(n) ∈ Ο(g1(n)) y f2(n) ∈ Ο(g2(n)) entonces: f1(n)+f2(n) ∈ Ο(maximo(g1(n),g2(n))). f1(n)+f2(n) ∈ Ο (g1(n)+g2(n)). Ambas son correctas.

Un algoritmo cuya talla es n y que tarda 40^n segundos en resolver cualquier instancia tiene una complejidad temporal: Θ ( n^n ). Θ ( 4^n ). Ninguna de las anteriores.

Si dos algoritmos tienen la misma complejidad asintótica: No necesitan exactamente el mismo tiempo para su ejecución. Necesitan exactamente el mismo tiempo para su ejecución. Ninguna de las anteriores.

Los algoritmos directos de ordenación, respecto de los indirectos: Presentan una mayor complejidad temporal y sus tiempos de ejecución absolutos son mayores. Presentan una menor complejidad temporal y sus tiempos de ejecución absolutos son menores. Presentan una mayor complejidad temporal si bien sus tiempos de ejecución absolutos son menores.

La talla o tamaño de un problema depende de: Conjunto de valores asociados a la entrada y salida del problema. Conjunto de valores asociados a la salida del problema. Conjunto de valores asociados a la entrada del problema.

En un algoritmo recursivo, la forma de dividir el problema en subproblemas: Influye en la complejidad espacial del mismo. Influye en su complejidad temporal. No influye en ninguna de sus complejidades.

f(n) = 5n+3m·n +11 entonces f(n) pertenece a: O (n·m). O (n^m). Las dos son correctas.

El sumatorio, desde i=1 hasta n, de i^k pertenece a: Ο(n^(k+1)). Ο(n^k). Ninguna de las anteriores.

La complejidad de la función A2 es: O( √n · a ). O( √n / a ). O( n / √a ).

Cual de las siguientes definiciones es cierta: Las cotas de complejidad se emplean cuando para una misma talla se obtienen diferentes complejidades dependiendo de la entrada al problema. Las cotas de complejidad se emplean cuando para diferentes tallas se obtienen diferentes complejidades dependiendo de la entrada al problema. Ninguna de las anteriores.

Cuando para distintas instancias de problema con el mismo tamaño no obtenemos el mismo resultado: No es posible calcular la complejidad a priori y debemos ejecutar el programa varias veces con la misma talla y obtener el tiempo medio para hallar la complejidad media. No se puede aplicar la técnica de paso de programa, ya que esta técnica es para calcular la complejidad a priori. Calculamos el máximo y mínimo coste que nos puede dar el algoritmo.

f(n) = 5n+5 ¿ f(n) pertenece a O(n)?. Sí. El valor de c es 5 y el valor mínimo de n0 es de 3. Sí. El valor de c es 9 y el valor mínimo de n0 es de 1. Sí. El valor de c es 6 y el valor mínimo de n0 es de 5.

f(n) = 10n+7 ¿ f(n) pertenece a O(n2)?. Sí. Para c = 1 y a partir de un valor de n0 =10. Sí Para cualquier valor de c positivo siempre existe un n0 a partir del que se cumple. No.

Si f(n) ∈ Ω (g(n)) entonces: ∃ c, n0∈ R+: f(n) ≥ c· g(n) ∀ n ≥ n0. ∃ c, n0∈ R+: f(n) ≥ c· g(n) ∀ n. ∃ c, n0∈ R+: f(n) ≤ c· g(n) ∀ n ≥ n0.

El coste asociado a la siguiente ecuación de recurrencia es: Θ(n lg(n^2) ). Θ(n^2 lg(n) ). Θ(n lg(n) ).