Algoritmia Parcial 1

La complejidad temporal en el mejor de los casos... es el tiempo que tarda el algoritmo en resolver la talla más pequeña que se le puede presentar. Las demás opciones son verdaderas. es una función de la talla que tiene que estar definida para todos los posibles valores de esta.

Sobre la complejidad temporal de esta función... Ninguna de las otras dos alternativas es cierta. Las complejidades en los casos mejor y peor son distintas. El mejor de los casos se da cuando n≤1 y en tal caso la complejidad es constante.

Con respecto al esquema Divide y vencerás, ¿es cierta la siguiente afirmación? Si la talla se reparte equitativamente entre los subproblemas, entonces la complejidad temporal resultante es una función logarítmica. No, nunca, puesto que también hay que añadir el coste de la división en subproblemas y la posterior combinación. No tiene porqué, la complejidad temporal no depende únicamente del tamaño resultante de los subproblemas. Sí, siempre, en Divide y Vencerás la complejidad temporal depende únicamente del tamaño de los subproblemas.

¿Qué cota se deduce de esta relación de recurrencia?. f(n) ∈ Θ(n²). f(n) ∈ Θ(n). f(n) ∈ Θ(n log n).

De las siguientes expresiones, o bien dos son verdaderas y una es falsa o bien al contrario: dos son falsas y una es verdadera. Marca la que en este sentido es distinta a las otras dos. 2n³ - 10n² + 1 ∈ O(n³). n + n^(3/2) ∈ Ω(n). n + n^(3/2) ∈ Θ(n).

Si f1(n) ∈ O(g1(n)) y f2(n) ∈ O(g2(n)) entonces... Las otras dos alternativas son ciertas. f1(n) + f2(n) ∈ O(max(g1(n),g2(n))). f1(n) + f2(n) ∈ O(g1(n) + g2(n)).

La versión de Quicksort que utiliza como pivote la mediana del vector... no presenta caso mejor y pero distintos para instancias del mismo tamaño. es más eficiente si el vector está ya ordenado. es la versión con mejor complejidad en el mejor de los casos.

El siguiente fragmento del algoritmo de ordenación Quicksort reorganiza los elementos del vector para obtener una subsecuencia de elementos menores que el pivote y otra de mayores. Su complejidad temporal, con respecto al tamaño del vector v, que está delimitado por los valores pi y pf, es... Nota: la función swap tiene una complejidad temporal constante. lineal en cualquier caso. cuadrática en el peor de los casos. lineal en el caso peor y constante en el caso mejor.

Dada esta relación de recurrencia, ¿qué cota es verdadera?. f(n) ∈ Ω(2ⁿ). f(n) ∈ Θ(n²). f(n) ∈ Θ(2ⁿ).

¿Cuál es la solución a la siguiente relación de recurrencia?. f(n) ∈ Θ(log n). f(n) ∈ Θ(n/3). Ninguna de las otras dos es cierta.

Indica cuál es la complejidad, en función de n, de este fragmento. O(n²). O(n log n). O(n).

Indica cuál es la complejidad de esta función (los posibles resultados se expresan en función del tamaño del problema). O(n). O(n log n). O(n²).

¿Cuál es la complejidad temporal de esta función?. O(n log n). O(n²). Θ(n log n).

Indica cuál es la complejidad, en función de n, de este fragmento. O(log²(n)). O(n log n). O(n²).

En cuanto a la complejidad temporal de esta función... Las complejidades en el mejor y en el peor de los casos no coinciden. El mejor de los casos se da cuando n = 0, su complejidad es constante. Esta función no presenta casos mejor y peor puesto que sólo puede haber una instancia para cada una de las posibles tallas.