B2-T3 Tipos abstractos y Estructuras de datos.TAD y Algoritmos Flashcards
¿Qué es una Estructura de datos ?
Una forma de organizar los datos para que puedan usarse de manera eficiente.
Estructuras de datos primitivos
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.
Estructuras de datos abstractas
son estructuras de datos de nivel superior que se construyen utilizando tipos de datos primitivos y proporcionan operaciones más complejas y especializadas.
Algoritmo
Un conjunto de instrucciones paso a paso para resolver un problema específico.
Complejidad temporal
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.
Complejidad espacial
Una medida de la cantidad de memoria que utiliza un algoritmo, dependiendo de la cantidad de datos en los que está trabajando el algoritmo.
Big O Notation
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.
Recursión
Una técnica de programación donde una función se llama a sí misma.
Divide y Vencerás
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.
Fuerza Bruta
De manera sencilla y directa, el algoritmo consiste en probar todas las soluciones posibles y luego elegir la mejor.
BubbleSort( Ordenamiento de la burbuja)
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.
Complejidad temporal del BubbleSort
O(n²)
CocktailSort (Ordenamiento de la Burbuja bidireccional)
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.
Complejidad temporal del CocktailSort
O(n²)
Selection Sort (Ordenamiento por selección)
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.
Complejidad temporal de Selection Sort
O(n²)