Parcial 1 ADA

En función del parámetro n ¿cuál es la complejidad temporal de la siguiente función?. Θ(n log n). Θ(n²). Θ(n).

La versión de Quicksort que utiliza como pivote la mediana del vector... El hecho de que el vector estuviera previamente ordenado o no, no influye en la complejidad temporal de este algoritmo. se comporta peor cuando el vector ya está ordenado. se comporta mejor cuando el vector ya está ordenado.

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²) ⊂ Θ(n³). Ω(n³) ⊂ Ω(n²). O(n²) ⊂ O(n³).

Sea f(n) la solución de la relación de recurrencia f(n) = 2f(n/2) + n; f(1) = 1; Indicad cuál de estas tres expresiones es cierta: f(n) ∈ Θ(n). f(n) ∈ Θ(n²). f(n) ∈ Θ(n log n).

¿Cuál de las siguientes afirmaciones es correcta?. f(n) ∈ O(g(n)). g(n) ∉ O(h(n)). h(n) ∈ O(g(n)).

Para que la complejidad de un algoritmo presente caso mejor y peor distintos... ... es condición necesaria y suficiente que existan instancias distintas del problema con el mismo tamaño. ... es condición necesaria que existan instancias distintas del problema con el mismo tamaño. ... es condición suficente que existan instancias distintas del problema con el mismo tamaño.

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₂(n)) = Θ(log₃(n)). Θ(log(n²)) = Θ(log(n³)). Θ(log²(n)) = Θ(log³(n)).

¿Cuál es la complejidad temporal de la siguiente función recursiva?. Θ(n² log n). Θ(n²). Θ(2ⁿ).

Sea una versión del algoritmo de ordenación Quicksort en la que siempre se selecciona como pivote el elemento que ocupa la posición n/4 (división entera). ¿Cuál sería la complejidad temporal en el caso más desfavorable?. O(n). O(n log(n)). Θ(n²).

Sean las funciones f1(n) = n⁰.⁹⁹⁹⁹⁹⁹ log n f2(n) = 1000000n f3(n) = 1.000001ⁿ f4(n) = n² Desde el punto de vista asintótico, ¿cuál de las siguientes ordenaciones, de mejor a peor, es la correcta?. f2(n); f1(n); f4(n); f3(n). f1(n); f2(n); f4(n); f3(n). f1(n); f2(n); f3(n); f4(n).

Sea f(n) la solución de 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) = Θ(log(n)). f(n) = Θ(n log(n)).

La siguiente relación de recurrencia expresa la complejidad de un algoritmo recursivo, donde g(n) es una función polinómica: Di cuál de las siguientes afirmaciones es cierta. Si g(n) ∈ Θ(n²) la relación de recurrencia representa la complejidad temporal del algoritmo de ordenación mediante inserción binaria. Si g(n) ∈ Θ(n) la relación de recurrencia representa la complejidad temporal del algoritmo de ordenación Mergesort. Si g(n) ∈ Θ(1) la relación de recurrencia representa la complejidad temporal del algoritmo de búsqueda dicotómica.

Los algoritmos de ordenación Quicksort y Mergesort... tienen el mismo coste temporal asintótico tanto en el caso peor como en el caso mejor. tienen el mismo coste temporal asintótico en el caso peor. tienen el mismo coste temporal asintótico en el caso mejor.

Tenemos un vector ordenado de tamaño "n_o" y un vector desordenado de tamaño "n_d" y queremos obtener un vector ordenado con todos los elementos. ¿Qué será más rápido?. Insertar los elementos del vector desordenado (uno a uno) en el vector ordenado. Ordenar el desordenado y luego mezclar las listas. Depende de si "n_o" > "n_d" o no.

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 O(n²). La busqueda binaria en un vector ordenado requiere en el peor caso un tiempo en O(log n). La ordenación de un vector usando el algoritmo Quicksort requiere en el peor caso un tiempo en O(n²).

Las siguientes funciones calculan el valor de la potencia n-ésima de dos. ¿Cuál es más eficiente en cuanto a coste temporal?. La segunda pot2_2(n), es más eficiente que la otra. Las dos funciones son equivalentes en cuanto a coste temporal. La primera pot2_1(n), es más eficiente que la otra.

Con respecto al parámetro n. ¿Cuál es la complejidad temporal de la siguiente función?. Θ(n⁴). Θ(n³ log n). Θ(n³).

Si f ∈ Θ(g₁) y f ∈ Θ(g₂) entonces. f ∈ Θ(g₁ + g₂). f ∈ Θ(max(g₁, g₂)). f ∈ Θ(g₁ * g₂).

¿Qué se entiende por tamaño del problema?. El número de parámetros que componen el problema. La cantidad de espacio en memoria que se necesita para codificar una instancia de ese problema. El valor máximo que puede tomar una instancia cualquiera de ese problema.

Con respecto al parámetro n, ¿Cuál es la complejidad temporal de la siguiente función?. Θ(n³). Θ(n²). Θ(n² log n).

¿Qué algoritmo es asintóticamente más rápido, el Quicksort o el Mergesort?. como su nombre indica, el Quicksort. el Mergesort es siempre más rápido o igual (salvo una constante) que el Quicksort. Los dos son igual de rápidos ya que el coste temporal asintótico de ambos es O(n log n).

¿Cuál es la complejidad espacial del algoritmo Quicksort?. O(n log n). O(n). O(1).