Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Repaso > BII Tema 3 Secc2 Algoritmos > Flashcards

BII Tema 3 Secc2 Algoritmos Flashcards

1
Q

Complejidad temporal

A

El tiempo de cómputo (que tarda) para ejecutar un programa

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

Big O anotation

A

Es la curva que representa la complejidad temporal.
Cota superior (asíntota) respecto del tiempo que tarda un algoritmo.

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

Complejidad espacial

A

Si usa mucha o poca memoria. Para saber los recursos que necesitamos

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

Big O anotation.
De mejor comportamiento a peor

A

O (1) orden constante
O(log log N)
O(log N)
O(N)
O(N*log N)
O(N^2)
O(n^3)
O(C^n)
O(N!)
O(n^n)

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

Algoritmos ordenación
Clasificación según donde lo ordena

A

Externo - en disco (fichero)
Interno - en memoria

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

Algoritmos ordenación
Clasificación según tiempo que tarda

A

Naturales -minimo posible si está ordenado
No naturales -minimo posible si está inversamente ordenado

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

Familias algoritmos
Exchange sort

A

Basados en Intercambio de datos
Burbuja
Quick Sort
Cocktail o burbuja bidireccional

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

Familias algoritmos
Selección sort

A

Basados en cual es el siguiente elemento
Selección
Heapsort

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

Familias algoritmos
Inserción sort

A

Basado en el siguiente elemento donde la va a colocar
Inserccion
Shellsort

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

Familia algoritmo
Merge sort

A

Basado en mezcla
Merge sort

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

Familias algoritmos
Distribution sort

A

Distribuye, hace una clasificación. Necesita espacio adicional
Bucket Sort (bin sort)
Radix sort

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

Algoritmo burbuja (Bubble Sort)
Complejidad temporal.
Complejidad espacial
Clasificación

A

Complejidad temporal
Caso mejor - O (N) - si están ordenados los datos
Caso medio y peor - O (n^2)
Complejidad espacial
O (1)
Clasificación
Intercambio, natural
Descripción: deja el más grande el último y la segunda vuelta ya tiene n-1 elementos y repite. Se puede hacer creciente y decreciente

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

Algoritmo inserción directa
Complejidad temporal y espacial
Clasificacion

A

Complejidad temporal
caso mejor - O (N)
Caso peor y medio - O(n^2)
Complejidad espacial
O (1)
Clasificación
Insercion
Descripción: busca de uno a uno

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

Algoritmo quicksort
Complejidad temporal y espacial
Clasificacion

A

Complejidad temporal
Caso medio y mejor- O( N log(N))
Caso peor- O (n^2)
Complejidad espacial
O (log(N))
Clasificación
Divide y vence. Intercambio. No estable.
Descripción :Elección pivote pequeños a un lado y grandes al otro

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

Algoritmo merge sort
Complejidad temporal y espacial
Clasificacion

A

Complejidad temporal
Todos los casos O(log N)
Clasificación espacial
O(N)
Clasificación
Mezcla
Descripción:divide la lista en sublistas hasta llegar a un caso trivial. Recursividad. Y luego mezcla la sublista

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

Algoritmo heapsort monticulo
Complejidad temporal y espacial

A

Complejidad temporal
Todos los casos O (log (N)) estable
Complejidad espacial
O(1)
Descripción: encontrar el mayor y es la raíz. Y ya reconstruye como un monticulo

17
Q

Algoritmo seleccion
Complejidad temporal y espacial
Clasificacion

A

Complejidad temporal
O (n^2)
Complejidad espacial
O(1)
Descripción: busca el mínimo y lo pone el primero. Y así sucesivamente

18
Q

Algoritmo radix sort
Complejidad temporal y espacial
Clasificacion

A

Complejidad temporal
O (N*k) ; k=n° dígitos
Complejidad espacial
O(N+k)
Clasificación
Distribución
2 versiones LSD ( empieza dígito menos representativo, unidades derecha) y MSD (Empieza por el más representativo, el de la izquierda)
Lee dígito a digito

19
Q

Algoritmo Bin Sort o bucket sort
Complejidad temporal y espacial
Clasificacion

A

Complejidad temporal
caso mejor O(N) nota este encontré yoO (N+k) ; k= n° casilleros (buckets)
Peor caso o(n^2)
Complejidad espacial
O(N)
Clasificación
Distribucion. Ordenaciones parciales. En casillero por rango de valores

20
Q

Diseño: técnicas
divide y vence

A

Troceas el problema en 2 subproblema, y el subproblema en otros 2. Así puedes llegar a un caso trivial o caso base que ya sepas resolver

21
Q

Diseño : tecnicas
Programación dinamica
bottom Up / top down + memoizacion

A

Lo contrario que divide y vence.
Una vez tienes el camino para resolver el problema. A partir de un caso pequeño óptimo, va añadiendo cada vez problemas más grandes
Se suele usar después de divide y vence

22
Q

Diseño técnicas
Voraces

A

En cada paso intenta deducir la solución más óptima
Dijkstra, prim/kruskal

23
Q

Diseño técnicas
Probabilisticos

A

Introducen una variable aleatoria para resolver el problema
Ejemplo :Montecarlo las vegas, sherwood

24
Q

Diseño técnicas
Backtracking ( vuelta atrás)

A

Explora el árbol con todas las posibles soluciones ñ. Lo usas cuando no tienes ninguna estrategia. Tardan mucho

25
Q

Diseño : técnicas
Ramificación y poda

A

Va de la mano de backtracking.
Se da cuenta que por ahí ya pasaste y ha probado todas las posibilidades y por ahí no va la solución, lo desecha ( poda)

Repaso (37 decks)

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