Un algoritmo recursivo basado en el esquema divide y vencerás... Las demás opciones son verdaderas ... será más eficiente cuanto más equitativa sea la división en subproblemas. ... nunca tendrá una complejidad exponencial.
Sea f(n) la solución de la relación de recurrencia f(n) = f(n/2) + 1; f(1) = 1. Indicad cuál de estas tres expresiones es cierta: f(n) ∈ Θ( n ) f(n) ∈ Θ( n log(n) ) f(n) ∈ Θ( log(n) ).
De las siguientes expresiones, o bien dos son verdaderas y una falsa, o bien dos son falsas y una verdadera.
Marca la que (en este sentido) es distinta a las otras dos. O( n^2 ) ⊂ O( 2^(log2(n)) ) ⊂ O( 2^n ) O( n^2 ) ⊂ O( 2^(log2(n)) ) ⊆ O( 2^n ) O( 2^(log2(n)) ) ⊂ O( n^2 ) ⊂ O( 2^n ).
¿Cuál es la complejidad temporal de la siguiente función recursiva? Θ( 2^n ) Θ( n^2 log(n) ) Θ( n^2 ).
De las siguientes expresiones, o bien dos son verdaderas y una falsa, o bien dos son falsas y una verdadera.
Marca la que (en este sentido) es distinta a las otras dos. Ω( n^3) ⊂ Ω( n^2 ) Θ( n^2 ) ⊂ Θ( n^3 ) O( n^2 ) ⊂ O( n^3 ).
Para la complejidad de un algoritmo presente caso mejor y peor distintos... ... es condición necesaria que existan instancias distintas del problema con el mismo tamaño. ... es condición suficiente que existan instancias distintas del problema con el mismo tamaño. ... es condición necesaria y suficiente que existan instancias distintas del problema con el mismo tamaño.
Se dispone de un vector de tamaño n cuyos elementos están de antemano organizados formando un montículo (heap).¿Cuál sería la complejidad temporal de reorganizar el vector para que quede ordenado? O( n ) O( log(n) ) O(n log(n) ).
Indica cuál es la complejidad, en función de n, del fragmento siguiente: O( n log(n) ) O( n ) O( n^2 ).
Dada la siguiente relación de recurrencia, ¿Qué cota es verdadera? f(n) ∈ Θ( n ) f(n) ∈ Θ( n^2 log(n) ) f(n) ∈ Θ( n^2 ).
La versión Quicksort que utiliza como pivote el elemento del vector que ocupa la primer posición... ... El hecho de que el vector estuviera previamente ordenado o no, no influye en la complejidad temporal de este algoritmo ... se comporta mejor cuando el vector está ya ordenado ... se comporta peor cuando el vector ya está ordenado.
Dado el siguiente fragmento de código... (imagen)
Indica cuál de las siguientes expresiones es la que mejor refleja su complejidad temporal. ∑ log(j) Ninguna de las otras dos opciones son correctas ∑ log(i) .
Un vector de enteros de tamaño n tiene sus elementos estructurados en forma de montículo (heap). ¿Cuál es la complejidad temporal en el mejor de los casos de borrar el primer elemento del vector y reorganizarlo posteriormente para que siga manteniendo la estructura de montículo? Ninguna de las otras dos opciones es correcta Constante con el tamaño del vector O(n).
Un problema de tamaño n puede transformarse en tiempo O(n) en siete de tamaño n/7; por otro lado, la solución al problema cuando la talla es 1 requiere un tiempo constante.
¿Cuál de estas clases de coste temporal asintótico es la más ajustada? O( n log(n) ) O( n^2 ) O( n ).
Indica cuál es la complejidad en función de n del fragmento siguiente: O( n^2 ) O( n ) O( n log(n) ).
Un programa con dos bucles anidados uno dentro del otro. El primero hace n iteraciones aproximadamente y el segundo la mitad, tarda un tiempo... O( n^2 ) O( n log(n) ) O( n√n).
Sea f(n) la solución de la relación de recurrencia f(n) = 2*f(n/2) + n; f(1) = 1. Indicad cuál de estas tres expresiones es cierta: f(n) ∈ Θ( n^2 ) f(n) ∈ Θ( n log(n) ) f(n) ∈ Θ( n ).
Dada la siguiente relación de recurrencia, ¿Qué cota es verdadera? f(n) ∈ Θ( n^3 ) f(n) ∈ Θ( n ) f(n) ∈ Θ( n log(n) ).
¿Cuál es la complejidad temporal de la siguiente función recursiva? Θ( 2^n ) Θ( n^3 ) Θ( n^3 log(n) ).
Di cuál de estos resultados de coste temporal asintótico es falsa: La ordenación de un vector usando el algoritmo Mergesort requiere en el peor caso un tiempo en Ω( n^2 ) La ordenación de un vector usando el algoritmo Quicksort requiere en el peor caso un tiempo en Ω( n^2 ) La búsqueda binaria en un vector ordenado requiere en el peor caso un tiempo en O( log(n) ).
Sea f(n) la solución de la relación de recurrencia... (imagen)
Indicad cuál de estas tres expresiones es cierta: f(n) ∈ Θ( 2^n ) f(n) ∈ Θ( n^2 ) f(n) ∈ Θ( n ).
De las siguientes expresiones, o bien dos son verdaderas y una falsa, o bien dos son falsas y una verdadera.
Marca la que (en este sentido) es distinta a las otras dos. Ω( n^2) ⊂ Ω( n^3 ) Θ( n^2 ) ⊂ Θ( n^3 ) O( n^2 ) ⊂ O( n^3 ).
De las siguientes expresiones, o bien dos son verdaderas y una falsa, o bien dos son falsas y una verdadera.
Marca la que (en este sentido) es distinta a las otras dos. Θ(log^2(n)) = Θ(log(n^2)) Θ(log^2(n)) = Θ(log(n)) Θ(log(n)) = Θ(log(n^2)).
Un problema de tamaño n puede transformarse en tiempo O(n^3) en ocho de tamaño n/2; por otro lado, la solución al problema cuando la talla es 1 requiere un tiempo constante.
¿Cuál de estas clases de coste temporal asintótico es la más ajustada? O( n^2 log(n) ) O( n^3 ) O( n^3 log(n) ).
|
