Los algoritmos de ordenación Quicksort y Mergesort tienen en común... que ordenan el vector sin usar espacio adicional que se ejecutan en O(n) que aplican la estrategia divide y vencerás.
tenemos un conjunto de n enteros positivos y queremos encontrar el subconjunto de tamaño m de suma mínima Lo mas adecuado sería usar una técnica de ramificación y poda, aunque en el peor caso el coste temporal sería exponencial Para encotrar la solución habría que probar con todas las combinaciones posibles de m enteros, con lo que RyP no aporta nada con respecto a Backtrackin Una técnica voraz daría una solución óptima.
Marca la FALSA La ordenación de un vector usando el algoritmo Quicksort requiere en el peor caso un tiempo O(n^2) La ordenación de un vector usando Mergesort requiere en el caso peor un tiempo de O(n^2) La búsqueda binaria en un vector ordenado requiere en el peor caso un tiempo de O(log n).
La complejidad en el mejor de los casos... es una función de la talla, o 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 mas pequeña que se le puede presentar Las dos anteriores son ciertas.
Queremos generar todas las formas distintas de mezclar n substancias de forma que el peso no supere el gramo. Queremos hacer un programa que genere todas las combinaciones posibles No hay ningún problema en usar Backtrackin' No se puede usar Backtrackin' porque las decisiones no son valores discretos No se puede usar backtrackin' porque el número de combinaciones es infinito.
Dado un problema de optimización, se puede usar backtrackin cuando... Es condición necesaria, (aunque no suficiente) que el dominio de decisiones sea discreto o discretizable Es condición necesaria y suficiente que el dominio de decisiones sea discreto o discretizable De cumplirse que se puedan emplear mecanismos de poda basados en la mejor solución hasta el momento.
Marca la CORRECTA O(2^log(n)) C O(n^2) C (2^n) O(n^2) C O(2^log(n)) C O(2^n) O(n^2) C O(2^log(n)) C O(2^n).
sea f(n) la solución de f(n) = 2f(n/2) + n, f(1) = 1 f(n) C O(n^2) f(n) C O(n log n) f(n) C O(n).
marca la FALSA (coste medio)(n/2) = O(n) (coste medio)(n) C O(n) (coste medio) (n) C (coste medio) (n^2).
Indica el coste de Es O(n^2) (caso peor) pero O(n^2) (caso mejor) Es O(n^2) Es O(n).
En un programa con dos bucles anidados, cada uno de los cuáles hace n iteraciones tarda: O(n^2) O(2^n) O(n).
La eficiencia de los algoritmos voraces se basa en El hecho de que, con antelación, las posibles decisiones se ordenan de mejor a peor El hecho de que las decisiones tomadas no se reconsideran En el esquema voraz no se puede hablar de eficiencia.
Sea f(n) = 2f(n - 1) + 1 f(n) C O(n^2) f(n) C O(2^n) f(n) C O(n).
Pertenence 3n^2 + 3 a O(n^3) No Solo para c = 1 y n0 = 5 Sí.
Las relaciones de recurrencia... aparecen sólo cuando la solución sea del tipo divide y vencerás expresan recursivamente el coste temporal de un algoritmo sirven para reducir el coste temporal de una solución cuando es prohibitivo.
Que algoritmo es mas rápido, quicksort o mergesort? como su nombre indica, el quicksort son los dos igual de rápidos: O(nlog(n)) el mergesort es siempre más rápido .
El coste temporal del algoritmo de ordenación por inserción es O(n^2) O(n) O(n log(n)).
Los algoritmos de programación dinámica hacen uso... de que la solución óptima se puede construir añadiendo el componente óptimo de los restantes, uno a uno de que se puede ahorrar esfuerzo guardando los resultados de esfuerzos anteriores de una estrategia trivial consistente en examinar todas las soluciones posibles.
Cual de estos tres problemas de optimización no tiene solución voraz óptima mochila continua mochila discreta árbol de recubrimiento de coste mínimo.
Marca la falsa 2n^2 + 3n + 1 C O(n^3) n + nlog(n) C O(cota inferior)(n) n + nlog(n) C O(coste medio)(n).
La solución ingenua a un problema de optimización, por un lado se basa en obtener soluciones óptimas a problemas parciales mas pequeños, y por otro, estos subproblemas se resuelven más de una vez. Este problema tiene una solución alternativa basada en... Divide y vencerás Programación dinámica Voraz.
Un algoritmo recursivo basado en divide y vencerás será mas eficiente cuanto mas equitativa sea la división en subproblemas Las demás son ciertas Nunca tendrá complejidad exponencial.
Marca la falsa 3n^2 + 1 C O(n^3) n + nlog(n) C (cota inferior) (n) n + n log(n) C (coste medio) (n).
O(n log n) O(n^2) O(n).
O(n^2) O(2^n) O(n^2 log n).
sea f(n) = 2f(n/2) + f, f(1) = 1 f(n) C O(n) f(n) C O(n^2) f(n) C O(n log(n)).
O(n log(n)) O(n) O(n^2).
f(n) = Vn + 3f(n/3) f(n) C O(n) f(n) C O(n^3) f(n) C O(Vn log n).
Un programa con dos bucles anidados, el primero hace n iteraciones y el segundo la mitad... O(n log(n)) O(n^2) O(nVn).
Los algoritmos de programación dinámica hacen uso de... que la solución óptima se puede construir añadiendo a la solución el elemento óptimo de los elementos restante, uno a uno que se puede ahorrar cálculos guardando resultados anteriores en un almacén una estrategia trivial consistente en examinar todas las posibles soluciones.
Que problema se da, y como se puede resolver, cuando se calcula el coeficiente binomial La recursión puede ser infinita y por tanto es necesario organizarla según el esquema iterativo del programa Se repiten muchos cálculos y ello se puede evitar haciendo uso de una estrategia voraz Se repiten muchos cálculos y ello se puede evitar usando programación dinámica.
f(n) = 2f(n/2) + n, f(1) = 1 f(n) C O(n^2) f(n) C O(n) f(n) C O(n log(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 dentro del programa con el mismo tamaño es condición suficiente que existan instancias distintas del problema con el mismo tamaño.
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 Las demás son falsas siempre coincidirá con la complejidad temporal de las instancias que están en el caso base del algoritmo recursivo.
f(n) = n^2 + 3f(n/3) O(n^2) O(n^2 log n) O(n).
Cuando se resuelve, usando Backtrackin', un problema de n decisiones, en el que siempre hay como mínimo dos opciones por decisión, cual de estas complejidades en el caso peor es la mejor que nos podemos encontrar O(2^n) O(n!) O(n^2).
Al resolver el problema del viajante de comercio con Backtrackin', cual de estas es una buena cota pesimista? se multiplica n por la distancia de la arista más corta que nos queda por considerar se ordenan las aristas restante de menor a mayor distancia y se calcula la suma de las n ciudades se resuelve el problema usando un algoritmo voraz que añade cada vez al camino el vértice más cercano al último añadido.
La complejidad en el caso peor un algoritmo RyP puede ser exponencial con el número de alternativas por cada decisión puede ser polinómica con el número de decisiones a tomar es exponencial con el número de decisiones a tomar.
La estrategia de RyP genera genera las soluciones posibles mediante... un recorrido guiado por estimaciones de las mejores ramas del árbol que representa el espacio de soluciones un recorrido en profundidad del árbol que representa el espacio de soluciones un recorrido en anchura del árbol que representa el espacio de soluciones.
Para que sirven las cotas pesimstas en RyP Para tener la certeza de que la cota optimista está bien calculada Para descartar nodos basándose en la preferencia por algún otro nodo ya completado Para descartar nodos basándose en el beneficio esperado.
La ventaja de RyP frente a Backtrackin' es que la primera genera las soluciones posibles al problema mediante.. un recorrido guiado por la cola de prioridad de donde se extraen primero los nodos que representan subárboles más prometedores del espacio de soluciones Las otras dos son verdaderas Un recorrido guiado por estimaciones de las mejores ramas del árbol que representa el espacio de soluciones.
Cuando resolvemos un problema mediante RyP los valores entre los cuales se elige en cada una de las decisiones tienen que formar un conjunto finito las decisiones solo pueden ser binarias los valores entre los cuales se elige en cada una de las decisiones pueden formar un conjunto infinito.
en RyP cada nodo tiene su propia cota optismita y pesimista cada nodo tiene su propia cota pesimista, la optimista sin embargo, es común a todos los nodos cada nodo tiene su propia cota optimista, la pesimista sin embargo es común a todos los nodos.
Para resolver un mismo problema usamos un algoritmo de RyP y lo modificamos para convertirlo en Backtrackin' Cambiamos la función que damos a la cota pesimista Provocamos que las cotas optimistas pierdan eficacia Sería necesario comprobar si las soluciones son factible o no puesto que RyP solo genera nodos factibles.
Cual de estas tres estrategias voraces obtiene un mejor valor para la mochila discreta Meter primero los elementos de menor peso Meter primero los elementos de mayor valor específico o valor por unidad de peso Meter primero los elementos de mayor valor.
|
