Parcial1 Flashcards
¿Qué es un algoritmo?
Una serie finita de instrucciones no ambiguas.
¿Para qué se usan las relaciones de recurrencia?
Para expresar la complejidad temporal de algoritmos recursivos.
¿Qué indica la notación Θ (Theta)?
Cota ajustada de complejidad: acota superior e inferiormente el tiempo de ejecución.
¿Cuándo se usa el Teorema Maestro?
Para resolver relaciones de recurrencia de algoritmos divide y vencerás.
¿Qué es la complejidad espacial?
Se refiere a la cantidad de memoria adicional que necesita el algoritmo.
¿Cuál es la complejidad de Mergesort?
Θ(n log n).
¿Cuál es la ecuación de recurrencia de Mergesort?
T(n) = n + 2T(n/2)
¿Qué técnica usa Mergesort?
Divide y vencerás.
¿Qué partes tiene el esquema Divide y Vencerás?
División, resolución recursiva, combinación.
¿Qué es el caso base en un algoritmo recursivo?
Situación más simple que se resuelve directamente.
¿Qué representa la notación O (grande)?
Una cota superior asintótica del tiempo de ejecución.
¿Cuándo se considera que un algoritmo es eficiente?
Cuando tiene una complejidad polinómica.
¿Qué es la función merge en Mergesort?
Fusión de dos listas ordenadas en una lista ordenada.
¿Qué complejidad tiene la función merge?
Θ(n), donde n es la suma de longitudes de las dos listas.
¿Qué es is_simple en el esquema Divide y Vencerás?
Condición que indica si un problema es lo bastante pequeño para resolverse sin dividir.
¿Qué significa que los subproblemas sean del mismo tamaño?
Permite aplicar directamente el Teorema Maestro.
¿Qué representa el coste g(n) en una relación de recurrencia?
El tiempo de ejecución en dividir y combinar sin contar llamadas recursivas.
¿Qué sucede si g(n) ∈ Θ(n)?
La complejidad total puede ser Θ(n log n) si los subproblemas están balanceados.
¿Qué significa a = b^k en el Teorema Maestro?
Implica una complejidad de Θ(n^k log n).
¿Qué es Quicksort?
Algoritmo de ordenación basado en Divide y Vencerás que usa un pivote.
¿Cuándo tiene Quicksort su peor caso?
Cuando el pivote divide muy desbalanceadamente.
¿En qué caso Quicksort tiene mejor eficiencia?
Cuando el pivote es la mediana.
¿Qué complejidad tiene Quicksort en el mejor caso?
Θ(n log n).
¿Complejidad de quicksort en el peor caso?
Θ(n^2).
¿Qué técnica usa Quicksort para dividir?
Seleccionar un pivote y particionar el vector.
¿Qué ocurre si no hay combinación en Divide y Vencerás?
Se omite el paso final como en Quicksort.
¿Cuál es el coste del algoritmo de las Torres de Hanoi?
Θ(2^n).
¿Qué ecuación de recurrencia describe las Torres de Hanoi?
T(n) = 1 + 2T(n - 1)
¿Por qué no se puede usar el Teorema Maestro con Hanoi?
Porque el tamaño de los subproblemas se reduce en n - 1, no en fracciones.
¿Cuál es la complejidad espacial de Mergesort sin contar la pila?
Θ(n), debido a la memoria auxiliar para merge.
¿Cuál es la complejidad de la pila de recursión en Mergesort?
Θ(log n).
¿Qué representa la función merge en Mergesort?
Fusiona dos listas ordenadas en una sola lista ordenada.
¿Cuál es la complejidad temporal de Mergesort?
Θ(n log n).
¿Qué ocurre si los subproblemas en Divide y Vencerás no son del mismo tamaño?
La eficiencia puede degradarse y no se puede aplicar directamente el Teorema Maestro.
¿Cuál es la ecuación de recurrencia asociada a Mergesort?
T(n) = n + 2T(n/2)
¿Cuál es el coste de memoria auxiliar en Mergesort sin contar la pila?
Θ(n)
¿Qué complejidad espacial tiene la pila de recursión en Mergesort?
Θ(log n)
¿Qué condiciones deben cumplirse para aplicar el Teorema Maestro?
Subproblemas del mismo tamaño y sin solapamiento.
¿Cuál es la complejidad del algoritmo de las Torres de Hanoi?
Θ(2^n)
¿Qué relación de recurrencia tiene el problema de Hanoi?
T(n) = 1 + 2T(n - 1)
¿Por qué no se puede aplicar el Teorema Maestro a las Torres de Hanoi?
Porque la reducción de tamaño es lineal, no fraccionaria.
¿Qué significa el término g(n) en la recurrencia T(n) = aT(n/b) + g(n)?
Es el coste de dividir y combinar sin contar las llamadas recursivas.
¿Qué valor de g(n) produce complejidad Θ(n log n) en el Teorema Maestro?
g(n) ∈ Θ(n)
¿Qué sucede si g(n) ∈ Θ(n^k) con k > log_b a en el Teorema Maestro?
La complejidad es Θ(n^k)
¿Qué sucede si g(n) ∈ Θ(n^k) con k < log_b a en el Teorema Maestro?
La complejidad es Θ(n^log_b a)
¿Qué sucede si g(n) ∈ Θ(n^k) con k = log_b a en el Teorema Maestro?
La complejidad es Θ(n^k log n)
¿Qué técnica de diseño usa el algoritmo Quicksort?
Divide y vencerás
¿Cuándo tiene Quicksort peor rendimiento?
Cuando el pivote divide los datos muy desigualmente.
¿Qué ocurre si Quicksort elige como pivote la mediana del vector?
Garantiza divisiones equilibradas y mejora el peor caso a Θ(n log n).
¿En qué consiste el paso de división en Quicksort?
Separar el vector en elementos menores y mayores que el pivote.
¿Cuál es la complejidad del paso de partición de Quicksort?
Θ(n)
¿Qué ocurre si el vector de entrada ya está ordenado en Quicksort?
Puede generar el peor caso si se elige mal el pivote.
¿Qué paso no es necesario en Quicksort respecto al esquema clásico de Divide y Vencerás?
La combinación de subresultados.
¿Qué función cumple is_simple(p) en el esquema Divide y Vencerás?
Determina si el problema es suficientemente pequeño para no dividirlo.
¿Qué hace la función combine(s) en el esquema Divide y Vencerás?
Fusiona las soluciones parciales de los subproblemas.
¿Qué representa a en la ecuación de recurrencia T(n) = aT(n/b) + g(n)?
El número de subproblemas en los que se divide el problema.
¿Qué representa b en la ecuación de recurrencia T(n) = aT(n/b) + g(n)?
La fracción del tamaño del problema original que tiene cada subproblema.
¿Qué significa la notación Θ?
Cota ajustada de complejidad: crece al mismo ritmo superior e inferior.
¿Qué significa la notación O (grande)?
Cota superior del crecimiento de una función.
¿Qué significa la notación Ω?
Cota inferior del crecimiento de una función.
¿Qué mide la complejidad espacial de un algoritmo?
La cantidad de memoria adicional necesaria durante la ejecución.
¿Qué mide la complejidad temporal de un algoritmo?
El número de operaciones elementales ejecutadas según el tamaño de entrada.
¿Cuál es el coste exacto del algoritmo Merge?
Θ(n), siendo n el número total de elementos a fusionar.
¿Qué ventaja aporta usar .reserve() en v_merged.reserve(last - first) en Merge?
Evita realocaciones dinámicas y mejora la eficiencia.
¿Qué tres fases incluye un algoritmo de Divide y Vencerás?
Dividir, resolver recursivamente, combinar.
¿Qué caracteriza a un problema apto para Divide y Vencerás?
Puede descomponerse en subproblemas más pequeños independientes.
¿Cuándo es útil usar relaciones de recurrencia?
Para analizar la eficiencia de algoritmos recursivos.
¿Qué representa n en la ecuación de recurrencia T(n) = n + 2T(n/2)?
El coste de dividir y combinar.
¿Qué define la eficiencia de un algoritmo?
Su comportamiento para entradas de gran tamaño.
¿Qué ocurre si los subproblemas contienen solapamientos?
No se puede aplicar directamente el Teorema Maestro.
