Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

ADA > Parcial1 > Flashcards

Parcial1 Flashcards

(70 cards)

Start Studying
1
Q

¿Qué es un algoritmo?

A

Una serie finita de instrucciones no ambiguas.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

¿Para qué se usan las relaciones de recurrencia?

A

Para expresar la complejidad temporal de algoritmos recursivos.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

¿Qué indica la notación Θ (Theta)?

A

Cota ajustada de complejidad: acota superior e inferiormente el tiempo de ejecución.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

¿Cuándo se usa el Teorema Maestro?

A

Para resolver relaciones de recurrencia de algoritmos divide y vencerás.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

¿Qué es la complejidad espacial?

A

Se refiere a la cantidad de memoria adicional que necesita el algoritmo.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

¿Cuál es la complejidad de Mergesort?

A

Θ(n log n).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

¿Cuál es la ecuación de recurrencia de Mergesort?

A

T(n) = n + 2T(n/2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

¿Qué técnica usa Mergesort?

A

Divide y vencerás.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

¿Qué partes tiene el esquema Divide y Vencerás?

A

División, resolución recursiva, combinación.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

¿Qué es el caso base en un algoritmo recursivo?

A

Situación más simple que se resuelve directamente.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

¿Qué representa la notación O (grande)?

A

Una cota superior asintótica del tiempo de ejecución.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

¿Cuándo se considera que un algoritmo es eficiente?

A

Cuando tiene una complejidad polinómica.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

¿Qué es la función merge en Mergesort?

A

Fusión de dos listas ordenadas en una lista ordenada.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

¿Qué complejidad tiene la función merge?

A

Θ(n), donde n es la suma de longitudes de las dos listas.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

¿Qué es is_simple en el esquema Divide y Vencerás?

A

Condición que indica si un problema es lo bastante pequeño para resolverse sin dividir.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

¿Qué significa que los subproblemas sean del mismo tamaño?

A

Permite aplicar directamente el Teorema Maestro.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

¿Qué representa el coste g(n) en una relación de recurrencia?

A

El tiempo de ejecución en dividir y combinar sin contar llamadas recursivas.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

¿Qué sucede si g(n) ∈ Θ(n)?

A

La complejidad total puede ser Θ(n log n) si los subproblemas están balanceados.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

¿Qué significa a = b^k en el Teorema Maestro?

A

Implica una complejidad de Θ(n^k log n).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

¿Qué es Quicksort?

A

Algoritmo de ordenación basado en Divide y Vencerás que usa un pivote.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

¿Cuándo tiene Quicksort su peor caso?

A

Cuando el pivote divide muy desbalanceadamente.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

¿En qué caso Quicksort tiene mejor eficiencia?

A

Cuando el pivote es la mediana.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

¿Qué complejidad tiene Quicksort en el mejor caso?

A

Θ(n log n).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

¿Complejidad de quicksort en el peor caso?

A

Θ(n^2).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
¿Qué técnica usa Quicksort para dividir?
Seleccionar un pivote y particionar el vector.
26
¿Qué ocurre si no hay combinación en Divide y Vencerás?
Se omite el paso final como en Quicksort.
27
¿Cuál es el coste del algoritmo de las Torres de Hanoi?
Θ(2^n).
28
¿Qué ecuación de recurrencia describe las Torres de Hanoi?
T(n) = 1 + 2T(n - 1)
29
¿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.
30
¿Cuál es la complejidad espacial de Mergesort sin contar la pila?
Θ(n), debido a la memoria auxiliar para merge.
31
¿Cuál es la complejidad de la pila de recursión en Mergesort?
Θ(log n).
32
¿Qué representa la función merge en Mergesort?
Fusiona dos listas ordenadas en una sola lista ordenada.
33
¿Cuál es la complejidad temporal de Mergesort?
Θ(n log n).
34
¿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.
35
¿Cuál es la ecuación de recurrencia asociada a Mergesort?
T(n) = n + 2T(n/2)
36
¿Cuál es el coste de memoria auxiliar en Mergesort sin contar la pila?
Θ(n)
37
¿Qué complejidad espacial tiene la pila de recursión en Mergesort?
Θ(log n)
38
¿Qué condiciones deben cumplirse para aplicar el Teorema Maestro?
Subproblemas del mismo tamaño y sin solapamiento.
39
¿Cuál es la complejidad del algoritmo de las Torres de Hanoi?
Θ(2^n)
40
¿Qué relación de recurrencia tiene el problema de Hanoi?
T(n) = 1 + 2T(n - 1)
41
¿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.
42
¿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.
43
¿Qué valor de g(n) produce complejidad Θ(n log n) en el Teorema Maestro?
g(n) ∈ Θ(n)
44
¿Qué sucede si g(n) ∈ Θ(n^k) con k > log_b a en el Teorema Maestro?
La complejidad es Θ(n^k)
45
¿Qué sucede si g(n) ∈ Θ(n^k) con k < log_b a en el Teorema Maestro?
La complejidad es Θ(n^log_b a)
46
¿Qué sucede si g(n) ∈ Θ(n^k) con k = log_b a en el Teorema Maestro?
La complejidad es Θ(n^k log n)
47
¿Qué técnica de diseño usa el algoritmo Quicksort?
Divide y vencerás
48
¿Cuándo tiene Quicksort peor rendimiento?
Cuando el pivote divide los datos muy desigualmente.
49
¿Qué ocurre si Quicksort elige como pivote la mediana del vector?
Garantiza divisiones equilibradas y mejora el peor caso a Θ(n log n).
50
¿En qué consiste el paso de división en Quicksort?
Separar el vector en elementos menores y mayores que el pivote.
51
¿Cuál es la complejidad del paso de partición de Quicksort?
Θ(n)
52
¿Qué ocurre si el vector de entrada ya está ordenado en Quicksort?
Puede generar el peor caso si se elige mal el pivote.
53
¿Qué paso no es necesario en Quicksort respecto al esquema clásico de Divide y Vencerás?
La combinación de subresultados.
54
¿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.
55
¿Qué hace la función combine(s) en el esquema Divide y Vencerás?
Fusiona las soluciones parciales de los subproblemas.
56
¿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.
57
¿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.
58
¿Qué significa la notación Θ?
Cota ajustada de complejidad: crece al mismo ritmo superior e inferior.
59
¿Qué significa la notación O (grande)?
Cota superior del crecimiento de una función.
60
¿Qué significa la notación Ω?
Cota inferior del crecimiento de una función.
61
¿Qué mide la complejidad espacial de un algoritmo?
La cantidad de memoria adicional necesaria durante la ejecución.
62
¿Qué mide la complejidad temporal de un algoritmo?
El número de operaciones elementales ejecutadas según el tamaño de entrada.
63
¿Cuál es el coste exacto del algoritmo Merge?
Θ(n), siendo n el número total de elementos a fusionar.
64
¿Qué ventaja aporta usar .reserve() en v_merged.reserve(last - first) en Merge?
Evita realocaciones dinámicas y mejora la eficiencia.
65
¿Qué tres fases incluye un algoritmo de Divide y Vencerás?
Dividir, resolver recursivamente, combinar.
66
¿Qué caracteriza a un problema apto para Divide y Vencerás?
Puede descomponerse en subproblemas más pequeños independientes.
67
¿Cuándo es útil usar relaciones de recurrencia?
Para analizar la eficiencia de algoritmos recursivos.
68
¿Qué representa n en la ecuación de recurrencia T(n) = n + 2T(n/2)?
El coste de dividir y combinar.
69
¿Qué define la eficiencia de un algoritmo?
Su comportamiento para entradas de gran tamaño.
70
¿Qué ocurre si los subproblemas contienen solapamientos?
No se puede aplicar directamente el Teorema Maestro.

ADA (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions