Tema3_Seccion2_Algoritmos Flashcards Preview
¿Cual es una de las condiciones principales que debe de tener un algoritmo?
debe ser finito
¿A que se refiere “Divide y vence”?
A una tecnica de diseño de algoritmos “top-down”
¿Que optimizaciónes se pueden aplicar a la técnica de “Divide y vence”?
- Programación dinamica
- Memoizacion de funciones
¿En que consiste la técnica de programación dinámica?
En combinar soluciones optimas de subproblemas para alcanzar la solución general optimiza
Nombre dos tipos de algoritmos probabilisticos
- Montecarlo
- Las vegas
¿Que mide la expresión O(n)?
La complejidad asintotica (espacial o temporal) de un algoritmo. Es una cota superior
¿Qué tipo de algoritmo es HeapSort?
De selección
¿En que se basa el HeapSort?
En crear una estructura de monticulo en un array e ir extrayendo la cima del mismo (que siempre será el MAX o el MIN del monticulo)
Nombre dos algoritmos de ordenacion que no se basan en realizar comparaciones entre sus elementos
- Bucket Sort
- Radix Sort
¿Que algoritmo de ordenacion se basa en calcular el digito más o menos significativo de cada elemento?
Radix Sort
¿Qué es un algoritmo estable?
Aquel que mantiene el orden relativo original de los registros que tengan el mismo valor en de clave
¿Cual es el caso peor para QuickSort y porque?
O(n2) si el pivote se elige mal y no particiona bien el array
Dado un array A, ordenado desde 1 a j:
- realizamos una busqueda binaria en el intervalo [1 , j] para ver donde colocar el elemento A[j+1]
- desplazamos, dentro del intervalo [1 , j] , todos los elementos mayores que A[j+1] hacia la derecha una posición
- insertamos A[j+1] en la posicion que nos dio el paso1
¿De que metodo de ordenación se trata?
Inserción binaria
Ordene de forma creciente las siguientes complejidades O(n!) , O(2n), O(nlog(n)), O(n2)
O(nlog(n)) → O(n2) → O(2n) → O(n!)
