B2-T3 Tipos abstractos y Estructuras de datos.TAD y Algoritmos Flashcards

1
Q

¿Qué es una Estructura de datos ?

A

Una forma de organizar los datos para que puedan usarse de manera eficiente.

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

Estructuras de datos primitivos

A

son estructuras de datos básicas proporcionadas por los lenguajes de programación para representar valores únicos: números enteros, números de punto flotante, caracteres y valores booleanos.

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

Estructuras de datos abstractas

A

son estructuras de datos de nivel superior que se construyen utilizando tipos de datos primitivos y proporcionan operaciones más complejas y especializadas.

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

Algoritmo

A

Un conjunto de instrucciones paso a paso para resolver un problema específico.

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

Complejidad temporal

A

Una medida de la cantidad de tiempo que tarda un algoritmo en ejecutarse, dependiendo de la cantidad de datos en los que está trabajando el algoritmo.

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

Complejidad espacial

A

Una medida de la cantidad de memoria que utiliza un algoritmo, dependiendo de la cantidad de datos en los que está trabajando el algoritmo.

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

Big O Notation

A

Notación matemática que describe el comportamiento límite de una función cuando el argumento tiende hacia un valor particular o infinito. Se utiliza para describir la complejidad temporal de un algoritmo.

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

Recursión

A

Una técnica de programación donde una función se llama a sí misma.

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

Divide y Vencerás

A

Un método para resolver problemas complejos dividiéndolos en subproblemas más pequeños y manejables, resolviendo los subproblemas y combinando las soluciones. A menudo utiliza las recursividad.

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

Fuerza Bruta

A

De manera sencilla y directa, el algoritmo consiste en probar todas las soluciones posibles y luego elegir la mejor.

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

BubbleSort( Ordenamiento de la burbuja)

A

Algoritmo estable. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Revisar varias veces toda la lista hasta que no se necesiten más intercambios.

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

Complejidad temporal del BubbleSort

A

O(n²)

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

CocktailSort (Ordenamiento de la Burbuja bidireccional)

A

Algoritmo estable. Mejora del BubbleSort. Ordena al mismo tiempo por los dos extremos del vector de manera que tras la primera iteración, tanto el menor como el mayor elemento estarán en sus posiciones finales, reduciendo el número de comparaciones finales.

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

Complejidad temporal del CocktailSort

A

O(n²)

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

Selection Sort (Ordenamiento por selección)

A

Algoritmo inestable. Revisa cada elemento de la lista hasta encontrar el valor más bajo, lo SELECCIONA y lo mueve el valor más bajo al frente de la parte no ordenada de la lista. Repasa la matriz nuevamente tantas veces como valores haya en la lista.

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

Complejidad temporal de Selection Sort

A

O(n²)

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

Insertion Sort (Ordenamiento por Insercion)

A

Algoritmo estable. Utiliza una parte de la matriz para contener los valores ordenados y la otra parte de la matriz para contener los valores que aún no están ordenados.
El algoritmo toma un valor a la vez de la parte no ordenada de la matriz y lo coloca en el lugar correcto en la parte ordenada de la matriz, hasta que la matriz esté ordenada.

18
Q

Complejidad temporal de Insertion Sort

A

O(n²)

19
Q

Binary Insertion Sort (Ordenación por inserción binaria)

A

Mejora del algoritmo de ordenamiento por inserción. Partiendo de una lista ya ordenada( la primera sería el primer elemento de la lista), se van introduciendo por búsquedas binarias elementos a la misma.

20
Q

Quicksort

A

Algoritmo inestable. Toma una matriz de valores, elige uno de los valores como elemento ‘pivote’ y mueve los otros valores para que los valores más bajos estén a la izquierda del elemento pivote y los valores más altos a la derecha de él.

21
Q

Complejidad temporal Quicksort

A

Promedio: O(n log n),
peor caso: O(n²)

22
Q

Counting sort (Ordenamiento por cuentas)

A

Algoritmo estable. No comparativo. Ordena una matriz contando el número de veces que ocurre cada valor. Solo funciona con números enteros no negativos. Counting Sort es rápido cuando el rango de valores posibles k es menor que el número de valores n.

23
Q

Complejidad temporal Counting sort

A

O(n+k)

24
Q

Bucket sort o Bin Sort (Ordenamiento por casilleros)

A

Algoritmo estable. No comparativo. Distribuye todos los elementos a ordenar entre un número finito de casilleros. Cada casillero solo puede contener los elementos que cumplan unas determinadas condiciones, las cuales deben ser excluyentes entre sí. Luego cada casillero se ordena utilizando otro algoritmo o se llama recursivamente al método, para finalmente devolver los casilleros concatenados por orden.

25
Q

Complejidad temporal Bucket sort

A

O(n)

26
Q

Postman’s sort (algoritmo del cartero)

A

Variante del Bucket sort utilizada cuando los elementos a ordenar disponen de varias claves y/o subclaves, las cuales se utilizan para hacer varios ordenamientos sucesivos.

27
Q

Complejidad temporal Postman’s sort

A

O(cn) siendo c el número de claves que se utilizan para clasificar.

28
Q

Radix Sort (Ordenamiento Radix)

A

Algoritmo estable. El algoritmo ordena una matriz por dígitos individuales, comenzando con el dígito menos significativo (el que está más a la derecha).
Utiliza la base creando 10 depósitos (o contenedores) diferentes correspondientes al dígito que está enfocado, luego se vuelven a colocar en la matriz antes de pasar al siguiente dígito.
Es un algoritmo no comparativo que solo funciona con números enteros no negativos.

29
Q

Complejidad temporal Radix Sort

A

O(n⋅k)

30
Q

Cuando un algoritmo es estable?

A

Es un algoritmo que:
- mantiene el orden de los elementos con el mismo valor antes y después de la clasificación.
- mantiene el orden relativo que tenían originalmente los elementos con claves iguales.

31
Q

Merge Sort (Ordenamiento por mezcla)

A

Algoritmo estable. Utiliza la técnica de divide y vencerás. Ordenamiento por mezcla. Ordena una matriz dividiéndola primero en matrices más pequeñas y luego reconstruyendo la matriz de la manera correcta para que esté ordenada.

32
Q

Complejidad temporal de Merge Sort

A

O(n log n)

33
Q

Binary tree sort (Ordenamiento con ábol binario)

A

El ordenamiento con árbol binario es un algoritmo de ordenamiento, el cual ordena sus elementos haciendo uso de un árbol binario de búsqueda. Se basa en ir construyendo poco a poco el árbol binario introduciendo cada uno de los elementos, los cuales quedarán ya ordenados. Después, se obtiene la lista de los elementos ordenados recorriendo el árbol en inorden.

34
Q

Complejidad temporal Binary tree sort

A

O(n log n)

35
Q

Algoritmo de búsqueda lineal

A

El algoritmo de búsqueda lineal busca en una matriz y devuelve el índice del valor que busca. Si llega al final de la matriz y no encuentra el valor, devuelve -1 para indicar que no se encontró el valor.

36
Q

Complejidad temporal de algoritmo de búsqueda lineal

A

O(n)

37
Q

Algoritmo de búsqueda binaria

A

También conocida, como búsqueda de intervalo medio​ o búsqueda logarítmica, es un algoritmo de búsqueda que encuentra la posición de un valor en un lista ordenada.
Compara el valor con el elemento en el medio del array, si no son iguales, la mitad en la cual el valor no puede estar es eliminada y la búsqueda continúa en la mitad restante hasta que el valor se encuentre.

38
Q

Complejidad temporal del algoritmo búsqueda binaria

A

O(log2n)
en el peor de los casos es O(log n)

39
Q

HeapSort (Ordenamiento por montículos)

A

Algoritmo no estable, no recursivo. Consiste en almacenar todos los elementos del vector a ordenar en un montículo (heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado.

40
Q

Complejidad temporal de HeapSort

A

O(nlogn)

41
Q

Listas enlazadas

A
42
Q
A