Bloque2-Tema3-Algoritmos Flashcards
Que es un algoritmo?
Conjunto de reglas aplicadas sistematicamente a unos datos de entrada apropiados, resuelven un problema en un NUMERO FINITO de pasos elementales.
Medidas de expresion de un algoritmo.
-Diagramas de flujo
-Pseudocodigo.
-Sistemas formales.
Tecnicas de analisis y diseño?
-Divide y venceras
-Voraces(Opcion optima en cada paso) (Djistra/ A* / Prim /Kruskal)
-Probalisticas (Montecarlo/las vegas)
-Backtracking (Explora arbol soluciones)
-Ramificacion y poda
-Programacion dinamica (Combinar subproblemas optimos)
Que es la memoizacion (usada en resursividad)?
Es una técnica de optimización que se usa principalmente para acelerar los tiempos de cálculo, almacenando los resultados de la llamada a una subrutina en una memoria intermedia o búfer y devolviendo esos mismos valores cuando se llame de nuevo a la subrutina o función con los mismos parámetros de entrada.
Que es la Cota superior asintótica (Big O Notation)
Una cota superior asintótica es una función que sirve de cota superior de otra función cuando el argumento tiende a infinito.
Tiempo logaritmico ordenado de menos tiempo a mas.
O(1) / O(logN) / O(n) / O(NLogN) / O(N^2) / O(2^N) / O (N!)
Tipos de clasificacion de algoritmos.
-Interno (Memoria) o Externo (fichero)
-Natural/adaptativo (Tarda lo minimo si la entrada esta ordenada)
-Estable (Mantiene orden relativo original para claves iguales)-> Quiere decir que mantiene el orden de los valores duplicados, por ejemplo dos 3, va a tener en el orden que venian ordenados.
Algoritmos de ordenacion de tipo Exchange Sorts?
-Burbuja
-Quicksort
-Cocktail o burbuja bi-direccional
Algoritmos de ordenacion de tipo Selection Sorts?
-Seleccion
-HeapSort
Algoritmos de ordenacion de tipo Insertion Sorts?
-Insercion
-ShellSort (Insercion con pasos mas grandes)
Algoritmos de ordenacion de tipo Merge Sorts?
-Merge sort
Algoritmos de ordenacion de tipo Distribution Sorts?
-Bucket Sort/Binsort
-Radix Sort
ESTOS NO HACEN COMPARACIONES.
Complejidad logaritmica del algoritmo de burbuja
Mejor caso -> O (N)
Caso medio-> O (N^2)
peor caso-> O (N^2)
COmo funciona el algoritmo de burbuja?
Vamos desplazando el Nº mas grande que nos encontramos a base de comparaciones e intercambios entre elementos adyacentes.
Complejidad logaritmica del algoritmo de insercion directa
Mejor caso -> O (N)
Caso medio-> O (N^2)
peor caso-> O (N^2)
Como funciona el algoritmo de insercion directa?
1-> Busca el lugar que le corresponde a Xi dentro del subarray que ya esta ordenado.
2-> Desplaza a todos los elementos necesario para hacerle hueco a Xi
NOTA: Si en el paso 1 en lugar de comparar 1 a 1 realiza una busqueda binario, se denomina insercion binaria.
Complejidad logaritmica del algoritmo QuickSort
Mejor caso -> O (N log(N))
Caso medio-> O (N log(N))
peor caso-> O (N^2)
Como funciona el algoritmo de QuickSort?
1-Crea un pivote
2-Intercambio de elementos > Xi y elementos < Xi
3-Misma operativa para cada subarray(Resursivo)
Osease que divide un array y mete los grandes a un lado y los pequeños al otro.
Complejidad logaritmica del algoritmo MergeSort
Mejor caso -> O (N log(N))
Caso medio-> O (N log(N))
peor caso-> O (N log(N))
Como funciona el algoritmo de MergeSort?
1- Divide la lista en sublistas hasta llegar al caso trivial (Recursividad)
2- Mezcla dos sublistas para obtener una lista ordenada.
Complejidad logaritmica del algoritmo HeapSort O monticulos.
Mejor caso -> O (N log(N))
Caso medio-> O (N log(N))
peor caso-> O (N log(N))
Como funciona el algoritmo de HeapSort?
Consiste en meter todos los elementos del array de datos en un monticulo MAX y luego realizar N veces llamadas a eliminar_max(), lo que lo ordena en resultado decreciente.
Complejidad logaritmica del algoritmo de Seleccion.
Mejor caso -> O (N^2)
Caso medio-> O (N^2)
peor caso-> O (N^2)
Como funciona el algoritmo de Seleccion?
1-Busca el minimo y lo pones en la 1º posicion.
2-Busca el siguiente minimo a partir de la primera posicion y lo pones en la segunda, etc.
Complejidad logaritmica del algoritmo Radix Sort
O (N*K)
Como funciona el algoritmo Radix Sort?
Hay dos versiones:
LSD: Usa el digito menos significativo.
MSD: Usa el digito mas significativo.
ordena enteros procesando sus dígitos de forma individual. Va metiendo por digitos en colas/buckets.
Complejidad logaritmica del algoritmo Bucket Sort/Binsort?
O (N)
Como funciona el algoritmo Bucket Sort/Binsort?
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.
Mirar ejercicio resursividad. Imagen bloque 2 tema 3.
