ada preguntas teoricas

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

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

La complejidad temporal (o coste temporal asintótico) 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. ... es una función de la talla, o tamaño del problema, que tiene que estar definida para todos los posibles valores de ésta. Las otras dos opciones son ambas verdaderas.

Tenemos un vector desordenado y queremos obtener los tres elementos más pequeños. ¿Cual seria la complejidad temporal mas ajustada para hacerlo?. El logaritmo de la longitud del vector. Lineal con la longitud del vector. Cuadrática con la longitud del vector.

La complejidad temporal en el mejor de los casos de un algoritmo recursivo... Ninguna de las otras dos es verdadera. ... 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 estan en el caso base.

Supongamos que una solución recursiva a un problema de optimización muestra estas dos caracteristicas: por un lado, se basa en obtener soluciones optimas a problemas parciales mas pequeños, y por otro, estos subproblemas se resuelven más de una vez durante el proceso recursivo. Este problema es candidato a tener una solucion alternativa basada en ... ... un algoritmo de programación dinámica. ... un algoritmo voraz. ... un algoritmo del estilo de divide y vencerás.

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

Di cuál 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 un tiempo en O(n^2). La ordenación de un vector usando el algoritmo Mergesort requiere en el peor caso un tiempo en O(n^2). La búsqueda binaria en un vector ordenado requiere en el peor caso un tiempo en O(log n).

Tenemos un vector ordenado de tamaño n0 y un vector desordenado de tamaño nd y queremos obtener un vector ordenado con todos los elementos. ¿Que sera mas rapido?. Depende de si n0 > nd o no. Insertar los elementos del vector desordenado (uno a uno) en el vector ordenado. Ordenar el desordenado y luego mezclar las listas.

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

¿Qué se entiende por tamaño del problema?. El valor máximo que puede tomar una instancia cualquiera de ese 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.

¿Qué nos proporciona la media entre el coste temporal asintótico (o complejidad temporal) en el peor caso y el coste temporal asintótico en el mejor caso?. El coste temporal promedio. El coste temporal asintótico en el caso medio. En general, nada de interés.

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

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

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.

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