Podcast
Questions and Answers
¿Cuál es la capacidad de cálculo de una consola o GPU actual en teraFLOPS?
¿Cuál es la capacidad de cálculo de una consola o GPU actual en teraFLOPS?
Para medir el coste de un algoritmo, una de las aproximaciones es contar las instrucciones y multiplicar por su coste. ¿Cuál de las siguientes opciones NO se utiliza como tiempo por instrucción?
Para medir el coste de un algoritmo, una de las aproximaciones es contar las instrucciones y multiplicar por su coste. ¿Cuál de las siguientes opciones NO se utiliza como tiempo por instrucción?
En el ejemplo de la función de búsqueda, ¿qué afirmación es correcta si el valor x aparece en la última posición del vector?
En el ejemplo de la función de búsqueda, ¿qué afirmación es correcta si el valor x aparece en la última posición del vector?
¿Cuál es un enfoque menos práctico para medir la eficiencia de un algoritmo?
¿Cuál es un enfoque menos práctico para medir la eficiencia de un algoritmo?
Signup and view all the answers
¿Qué velocidad de cálculo corresponde a 1 exaFLOPS?
¿Qué velocidad de cálculo corresponde a 1 exaFLOPS?
Signup and view all the answers
¿Qué representa la cota inferior Ω(f(n))?
¿Qué representa la cota inferior Ω(f(n))?
Signup and view all the answers
¿Cuál es la relación correcta que define el orden exacto de dos funciones f(n) y g(n)?
¿Cuál es la relación correcta que define el orden exacto de dos funciones f(n) y g(n)?
Signup and view all the answers
¿Cuál de las siguientes afirmaciones sobre las cotas es incorrecta?
¿Cuál de las siguientes afirmaciones sobre las cotas es incorrecta?
Signup and view all the answers
La regla de la suma para las funciones complejidad establece que O(f + g) es igual a:
La regla de la suma para las funciones complejidad establece que O(f + g) es igual a:
Signup and view all the answers
Si una función f ∈ O(g) y g ∈ O(h), ¿qué implicación se puede derivar?
Si una función f ∈ O(g) y g ∈ O(h), ¿qué implicación se puede derivar?
Signup and view all the answers
¿Cuál es el menor número natural k tal que la función f(n) = 2n³ + n² log n esté en O(nk)?
¿Cuál es el menor número natural k tal que la función f(n) = 2n³ + n² log n esté en O(nk)?
Signup and view all the answers
¿Qué orden asintótico tiene el algoritmo potencia1 en el peor caso?
¿Qué orden asintótico tiene el algoritmo potencia1 en el peor caso?
Signup and view all the answers
Si f(n) = (n² + 17n + 3)², ¿cuál es el orden de f(n) en términos de n?
Si f(n) = (n² + 17n + 3)², ¿cuál es el orden de f(n) en términos de n?
Signup and view all the answers
¿Cómo se compara la función n² log n con la función n³?
¿Cómo se compara la función n² log n con la función n³?
Signup and view all the answers
¿Cuál es el orden asintótico de la función f(n) = (2n + n²)(n³ + 3n)?
¿Cuál es el orden asintótico de la función f(n) = (2n + n²)(n³ + 3n)?
Signup and view all the answers
En relación a O y ⌦, ¿cómo se comportan las funciones n³ y n² + 5n?
En relación a O y ⌦, ¿cómo se comportan las funciones n³ y n² + 5n?
Signup and view all the answers
En el algoritmo potencia2, ¿cuántas multiplicaciones realiza en el peor caso?
En el algoritmo potencia2, ¿cuántas multiplicaciones realiza en el peor caso?
Signup and view all the answers
¿Cuál es el menor orden g(n) tal que f(n) = n² + n³ esté en O(g(n))?
¿Cuál es el menor orden g(n) tal que f(n) = n² + n³ esté en O(g(n))?
Signup and view all the answers
¿Qué función de complejidad permite solucionar problemas 100 veces más grandes al aumentar la velocidad del computador?
¿Qué función de complejidad permite solucionar problemas 100 veces más grandes al aumentar la velocidad del computador?
Signup and view all the answers
Si un algoritmo tiene coste O(n^3) y se duplica la velocidad del computador, ¿cuánto más grande puede ser el problema que se resuelve?
Si un algoritmo tiene coste O(n^3) y se duplica la velocidad del computador, ¿cuánto más grande puede ser el problema que se resuelve?
Signup and view all the answers
En la jerarquía de órdenes de complejidad, ¿cuál de los siguientes algoritmos se considera tratable?
En la jerarquía de órdenes de complejidad, ¿cuál de los siguientes algoritmos se considera tratable?
Signup and view all the answers
¿Cuál de las siguientes afirmaciones sobre los costos de complejidad es incorrecta?
¿Cuál de las siguientes afirmaciones sobre los costos de complejidad es incorrecta?
Signup and view all the answers
Al duplicar el tiempo durante el cual un algoritmo puede ejecutarse, ¿qué impacto tiene en un algoritmo O(n)?
Al duplicar el tiempo durante el cual un algoritmo puede ejecutarse, ¿qué impacto tiene en un algoritmo O(n)?
Signup and view all the answers
¿Qué característica distingue a los algoritmos de complejidad polinómica?
¿Qué característica distingue a los algoritmos de complejidad polinómica?
Signup and view all the answers
Si un algoritmo O(n^2) toma 1 hora para un problema de tamaño n=100, ¿cuánto tiempo tomaría para n=141?
Si un algoritmo O(n^2) toma 1 hora para un problema de tamaño n=100, ¿cuánto tiempo tomaría para n=141?
Signup and view all the answers
¿Qué función de complejidad tiene un crecimiento tan rápido que apenas significa un aumento en el tamaño del problema cuando se duplica el tiempo o la velocidad?
¿Qué función de complejidad tiene un crecimiento tan rápido que apenas significa un aumento en el tamaño del problema cuando se duplica el tiempo o la velocidad?
Signup and view all the answers
¿Qué valor devuelve la función si la lista está llena?
¿Qué valor devuelve la función si la lista está llena?
Signup and view all the answers
¿Cuál es el propósito de la variable 'pos' en la función insertar?
¿Cuál es el propósito de la variable 'pos' en la función insertar?
Signup and view all the answers
En la función 'ordenar', ¿qué indica 'nuevo'?
En la función 'ordenar', ¿qué indica 'nuevo'?
Signup and view all the answers
¿Cuál es el tiempo medio de ejecución en el caso peor del algoritmo de ordenación por inserción?
¿Cuál es el tiempo medio de ejecución en el caso peor del algoritmo de ordenación por inserción?
Signup and view all the answers
En la función de inserción, ¿qué sucede si el elemento que se va a insertar ya está en la lista?
En la función de inserción, ¿qué sucede si el elemento que se va a insertar ya está en la lista?
Signup and view all the answers
¿Qué operación se realiza después de encontrar la posición adecuada para insertar en la función insertar?
¿Qué operación se realiza después de encontrar la posición adecuada para insertar en la función insertar?
Signup and view all the answers
¿Cuál es la complejidad temporal del algoritmo si 'buscar' es una búsqueda binaria?
¿Cuál es la complejidad temporal del algoritmo si 'buscar' es una búsqueda binaria?
Signup and view all the answers
¿Qué hace el bucle for en la función 'ordenar' después de identificar 'pos'?
¿Qué hace el bucle for en la función 'ordenar' después de identificar 'pos'?
Signup and view all the answers
¿Qué establece la regla del producto en relación con funciones de complejidad?
¿Qué establece la regla del producto en relación con funciones de complejidad?
Signup and view all the answers
Según el teorema del límite, bajo qué condiciones se cumple que f es O(g) y g es O(f)?
Según el teorema del límite, bajo qué condiciones se cumple que f es O(g) y g es O(f)?
Signup and view all the answers
¿Qué implica que f(n) está en O(g(n)) y el límite de f(n)/g(n) tiende a 0?
¿Qué implica que f(n) está en O(g(n)) y el límite de f(n)/g(n) tiende a 0?
Signup and view all the answers
¿Qué se puede concluir sobre dos funciones f y g cuando el límite de f(n)/g(n) tiende a +1?
¿Qué se puede concluir sobre dos funciones f y g cuando el límite de f(n)/g(n) tiende a +1?
Signup and view all the answers
¿Qué significa la relación f(n) = Θ(g(n))?
¿Qué significa la relación f(n) = Θ(g(n))?
Signup and view all the answers
¿Qué condición debe cumplirse para que se pueda afirmar que una función polinómica de grado m está en O(n^m)?
¿Qué condición debe cumplirse para que se pueda afirmar que una función polinómica de grado m está en O(n^m)?
Signup and view all the answers
El principio de dualidad se aplica cuando se establece que g(n) es O(f(n)). ¿Qué implica eso sobre f(n)?
El principio de dualidad se aplica cuando se establece que g(n) es O(f(n)). ¿Qué implica eso sobre f(n)?
Signup and view all the answers
¿Qué sucede si tenemos que el límite de f(n) * g(n) tiende a +1?
¿Qué sucede si tenemos que el límite de f(n) * g(n) tiende a +1?
Signup and view all the answers
Study Notes
Análisis de la eficiencia de los algoritmos
- El análisis de la eficiencia de los algoritmos es fundamental en la programación para comparar algoritmos y seleccionar la mejor opción para resolver problemas.
- La eficiencia se mide en términos de tiempo y espacio (memoria).
- Un algoritmo eficiente consume los recursos (tiempo y memoria) de forma mínima.
- Un algoritmo ineficiente puede consumir innecesariamente recursos.
- El crecimiento exponencial de los problemas puede representar un desafío.
¿Qué es un número grande?
- La pandemia de COVID-19 en 2020 mostró ejemplos de crecimiento exponencial en la propagación.
- Un ejemplo es que un número de infectados se duplica cada tres días.
- Un solo lirio de agua en un pantano puede cubrirlo en 30 días si su tamaño se duplica cada día.
- Ejemplos como el arroz y ajedrez muestra la rápida exponencialidad en las cantidades.
- Los problemas que crecen exponencialmente demuestran la importancia de los algoritmos eficientes.
Eficiencia
- La eficiencia de un programa se relaciona con los recursos que utiliza.
- Los recursos comunes en programación son el tiempo y el espacio (memoria).
- Un programa eficiente utiliza el mínimo tiempo y memoria posible.
- Un programa ineficiente consume innecesariamente tiempo y/o memoria.
- El análisis de costos de algoritmos es importante para la toma de decisiones en el desarrollo.
Cálculo explícito y funciones de coste
- Calcular el coste de un algoritmo de forma explícita implica contar las instrucciones que ejecuta.
- Cada instrucción tiene un coste asociado (por ejemplo, asignación, suma, comparación).
- Sumar esos costos da una estimación del tiempo de ejecución de cada algoritmo.
- Un enfoque poco práctico es contar cada paso y aplicarle su respectivo tiempo.
- La función de coste de un algoritmo se relaciona con su coste.
Ejemplos de cálculo de eficiencia explícito
- La eficiencia del programa puede variar dependiendo de la entrada.
- El caso mejor es cuando el programa encuentra el dato buscado rápidamente.
- El caso peor es cuando el programa debe buscar el dato buscado en toda la entrada.
- Costos constantes, como la asignación de una variable, tienen un coste de O(1)
- El caso más frecuente es lineal (proporcional al tamaño de las entradas) con coste de O(n)
- El caso de búsqueda binaria es logarítmico, O((log n))
Medidas asintóticas de eficiencia
- Las medidas asintóticas son importantes ya que no dependen de la tecnología concreta.
- Son necesarias para comparar algoritmos en términos de crecimiento del tiempo de ejecución.
- Pueden ignorarse las constantes multiplicativas y aditivas, en las funciones de coste para la comparación.
- El análisis se centra en valores de "n" (tamaño) suficientemente grandes.
- Se define el orden de complejidad usando notación O,Ω,Θ.
Análisis de eficiencia en algoritmos iterativos
- El cálculo del coste de los algoritmos iterativos se simplifica al considerar sólo el orden de magnitud.
- Se determina el orden de complejidad de un algoritmo en base al número de iteraciones y el coste de cada paso.
- Las reglas para el cálculo de la eficiencia (condición, bucles, llamadas a funciones etc.) ayudan a determinar la eficiencia en función del tamaño de entrada.
- En la práctica de desarrollo no se realiza un calculo exacto del tiempo de cada paso o instrucción, se busca simplificar.
Órdenes de complejidad
- Los órdenes de complejidad indican el crecimiento del tiempo de ejecución en función del tamaño de la entrada.
- Existen diferentes órdenes de complejidad con comportamientos distintos en el tiempo de ejecución; ejemplos incluyen: 0(1), 0(log n), 0(n), etc.
- La jerarquía de órdenes indica el crecimiento relativo de las funciones de coste.
- (0(1)) algoritmo constante, (0(log n)) algoritmo logarítmico, etc.
- Algunos ejemplos de algoritmos iterativos incluyen seleccion, producto de matrices donde el coste computacional se analiza por la instrucción crítica (la que tiene la frecuencia de ejecución más alta) y es calculado usando sumatorios.
Resumen del tema
- Distinguir entre el orden de complejidad en el caso mejor, peor, o promedio.
- Saber comparar las dos medidas de coste.
- Entender que el coste asintótico es sobre valores muy grandes.
- Saber calcular los costes exactos de programas iterativos.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Related Documents
Description
Pon a prueba tus conocimientos sobre algoritmos y su complejidad. Este cuestionario abarca desde conceptos de cálculo en teraFLOPS hasta cotas y orden asintótico. Responde preguntas clave para entender mejor la eficiencia de los algoritmos.
