Parcial I Intentos Algoritmia

La siguiente relación de recurrencia expresa la complejidad de un algoritmo recursivo, donde g(n) es una función polinómica. Cual de las siguientes afirmaciones es FALSA: Si g(n) ∈ Θ(n), la relación de recurrencia representa la complejidad temporal en el caso mejor del algoritmo de ordenación Quicksort. 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 en común... que aplican la estrategia de divide y vencerás. que se ejecutan en tiempo O(n). que ordenan el vector sin usar espacio adicional. Ninguna de las anteriores.

Sea el vector v[8]={8,6,4,5,4,3,2,2}, indica cual de las siguientes opciones es cierta: El vector v es un montículo máximo. El vector no es un montículo máximo porque el elemento v[2]=4 debe ser "hundido" (desplazado hacia derecha). El vector no es un montículo máximo porque el elemento v[3]=5 debe ser "flotado" (desplazado hacia izquierda).

Si f1∈ O(g1) y f2 ∈ O(g2), entonces... f1 + f2 ∈ O(g1 + g2). Ambas opciones son ciertas. f1 + f2 ∈ O(max(g1, g2)).

Dado un vector desordenado, queremos obtener los 3 elementos más pequeños. ¿Cuál sería la complejidad temporal más ajustada para hacerlo? Sin pérdida de generalidad puedes suponer que el vector todos los elementos son distintos. Cuadrática con la longitud del vector. Lineal con la longitud del vector. El logaritmo de la longitud del vector.

Con respecto a la complejidad temporal de la siguiente función, ¿cuál de las siguientes afirmaciones es correcta?. El coste temporal exacto de la función es O(n). La complejidad temporal en el mejor de los casos es cte. Las otras dos afirmaciones son falsas.

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

Con respecto al parámetro n,¿Cuál es la complejidad temporal de la siguiente función?. θ(n^2). θ(n^2log(n)). θ(n^3). Ninguna de las anteriores.

De las siguientes expresiones, o bien dos son verdaderas y una falsa, o bien dos son falsas y una es verdadera. Marca la que es distinta a las otras dos en este sentido: θ(log(n^2)) = θ(log(n^3)). θ(log^2(n)) = θ(log^3(n)). θ(log2(n)) = θ(log3(n)).

Di cual de estos resultados de coste temporal asintótico es FALSA: La ordenación de un vector usando el algoritmo Quicksort requiere en el peor caso O(n^2). La ordenación de un vector usando el algoritmo MergeSort requiere en el peor caso O(n^2). La búsqueda binaria en un vector ordenado requiere en el peor caso un tiempo en O(log(n)).

Obtener la complejidad temporal en el peor caso de la siguiente función: c_s(n) = n * sum_{j=1}^{log n} sum_{i=1}^j (1/2)^i ∈ O(n log n). c_s(n) = sum_{k=1}^{log n + 1} (n - n / 2^k) ∈ O(n log n). Ninguna es correcta. Ambas son ciertas.

Si f ∈ Θ(g1) y f ∈ Θ(g2): f ∈ Θ(g1+g2). f ∉ Θ(max(g1,g2)). Ambas son correctas.

Cuál de los siguientes algoritmos de ordenación necesita un espacio de almacenamiento adicional al vector que se ordena con complejidad O(n). Quicksort. Bubblesort. Mergesort.

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

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

¿Qué tiene en común el algoritmo que obtiene el k-ésimo elemento más pequeño de un vector y el algoritmo de ordenación Quicksort?. La combinación de las soluciones de los subproblemas. La división del problema en subproblemas. El número de llamadas recursivas que hacen. Ninguna de las anteriores.

Se pretende ordenar un vector cuyos n elementos están organizados formando un montículo. Sin tener en cuenta el tiempo empleado para este preproceso. ¿Cuál es el corte temporal asintótico de realizar la operación?. O(n). O(nlogn). Ninguna de las anteriores.

La complejidad temporal en el mejor de los casos de un algoritmo recursivo... ...es la complejidad temporal de las instancias que están en el caso base. ...coincide con el valor del caso base de la ecuación de recurrencia que expresa la complejidad temporal del algoritmo. Ninguna de las dos opciones anteriores es correcta.

En función del parámetro n, ¿cuál es la complejidad temporal asintótica de la siguiente función?. θ(n^2). θ(2^n). Ninguna de las anteriores.

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

La complejidad temporal en el mejor de los casos: ...es una función del tamaño del problema, que tiene que estar definida para todos los posibles valores de esta. ...es el tiempo que tarda el algoritmo en resolver la talla más pequeña. Ambas son correctas. Ninguna de las anteriores.

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 primera es más eficiente. La segunda es más eficiente. Las dos funciones son equivalentes en cuanto a coste temporal.

¿En qué caso la complejidad temporal del algoritmo de ordenación Quicksort es igual a la complejidad temporal del algoritmo Mergesort?. En el caso peor de ambos. En el caso mejor de ambos. Tanto en el caso peor como en el mejor de ambos.

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 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.

Sin considerar el espacio que ocupa la pila de recursión, ¿cuál es la complejidad espacial del algoritmo Quicksort?. Θ(1). Θ(nlogn). Θ(n).

Sin considerar el espacio que ocupa la pila de recursión, ¿cuál es la complejidad espacial del algoritmo Mergesort?. Θ(n). Θ(1). Θ(logn). Ninguna de las anteriores.

¿Cuál de las siguientes relaciones de recurrencia expresa mejor el número de llamadas recursivas que hace el algoritmo Mergesort?. T(n) = n + T(n/2), para n > 1 y T(n) = 1, para n < 2. T(n) = n + 2T(n/2) para n > 1 y T(n) = 1, para n < 2. T(n) = 1 + 2T(n/2) para n > 1 y T(n) = 1, para n < 2. Ninguna de las anteriores.

Si f ∉ O(g1), lim n→∞ (f(n)/g1(n)) existe y f ∈ O(g2), entonces siempre se cumplirá: f ∉ O(max(g1, g2)). f ∈ Ω(g1 + g2). f ∈ Ω(min(g1,g2)).

¿Qué nos proporciona la media entre el coste temporal asintótico en el peor caso y el coste temporal asintótico en el mejor caso?. En general, nada de interés. El coste temporal asintótico en el caso medio. El coste temporal promedio. Ninguna de las anteriores es correcta.

Con respecto a la complejidad espacial de los algoritmos de ordenación Quicksort, Heapsort y Mergesort, y sin considerar el espacio quepueda ocupar las posibles pilas de recursión: La complejidad espacial de todos ellos es lineal con el tamaño del vector a ordenar. Mergesort y Heapsort tienen complejidad espacial lineal con el tamaño del vector a ordenar, la de Quicksort es constante. Mergesort tiene complejidad espacial lineal con el tamaño del vector a ordenar, la de los otros dos es constante.

Los algoritmos de ordenación Quicksort y Mergesort: ...tienen el mismo coste temporal asintótico en el caso peor. ...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 mejor. ...no tienen el mismo coste temporal asintótico en ningún caso.

¿Qué tienen en común los algoritmos de ordenación Quicksort y Mergesort?. El número de llamadas recursivas que hacen en el mejor de los casos. La complejidad temporal de la división en subproblemas. La complejidad temporal de la combinación de las soluciones parciales.

De las siguientes expresiones, o bien son dos son verdaderas y una es falsa, o bien dos son falsas y una es verdadera. Marca la que es distinta a las otras dos, en este sentido. O(4^(log2(n))) ⊂ O(n) ⊂ O(2^n). O(2^(log2(n))) ⊂ O(n^2) ⊂ O(n!). O(n^2) ⊂ O(2^(log2(n))) ⊂ O(2^n).

Tenemos una lista ordenada de tamaño n, y una lista desordenada de tamaño m, queremos obtener una lista ordenada con todos los elementos. ¿Cuál sería la complejidad de insertar, uno a uno, todos los elementos de la lista desordenada en la ordenada?. O(mlogn). O(mn). O(m(n+m)). Ninguna de las anteriores.

Sea la siguiente relación de recurrencia: g(n) = n. g(n) = n^2. g(n) = nlogn. Ninguna de las anteriores.

De las siguientes expresiones, o bien dos son verdaderas y una es falsa, o bien dos son falsas y una es verdadera. Marca la distinta de las otras dos. O(2^log(n)) ⊆ O(n^2) ⊂ O(n!). O(n^2) ⊂ O(2^log(n)) ⊂ O (2^n). O(4^logn) ⊆ O(n^2) ⊂ O(2^n). No se cual es aun.

La complejidad temporal en el mejor de los casos de un algoritmo recursivo... ...coincide con el valor del caso base de la ecuación de recurrencia que expresa la complejidad temporal del algoritmo. ...es la complejidad temporal de las instancias que están en el caso base. Ninguna de las otras opciones es verdadera.

Di cual de estos resultados de coste temporal asintótico es FALSA : La ordenación de un vector usando Quicksort requiere en el peor caso un tiempo en Ω(n^2). La ordenación de un vector usando Mergesort requiere en el peor caso un tiempo en Ω(n^2). La búsqueda binaria en un vector ordenado requiere en el peor caso en O(logn). Ninguna de las anteriores.

De las siguientes expresiones, o bien dos son verdaderas y una es falsa, o bien dos son falsas y una es verdadera. Marca la distinta a las otras dos. Θ(log2(n)) = Θ(log3(n)). log(n^3) ∉ Θ(log3(n)). Θ((logn)^2) = Θ((long)^3).

Si f ∈ Ω(g1) y f ∈ Ω(g2), entonces: f ∈ Ω(g1+g2). f ∈ Ω(g1*g2). f ∉ Ω(min(g1,g2)). Ninguna de las anteriores.

Se quieren ordenar n números distintos comprendidos entre 1 y m. Para ello, se usa un array de m booleanos que se inicializan primero a false. A continuación, se recorren los n números cambiando los valores del elemento del vector de booleanos correspondiente a su número a true. Por último, se recorre el vector de booleanos escribiendo los índices de los elementos del vector de booleanos que son true. ¿Es este algoritmo más rápido que el Mergesort?. No, ya que este algoritmo ha de recorrer varias veces el vector de booleanos. Sólo si nlogn > km (siendo k una constante que depende de la implementación). Si, ya que el MergeSort es O(nlogn) y este es O(n).

Si f1 ∈ O(g1) y f2 ∈ O(g2), entonces... f1+f2 ∈ O(g1+g2). f1+f2 ∈ O(max(g1, g2)). Las otras dos opciones son ambas ciertas. Ninguna de las anteriores es cierta.