3_Algoritmos Flashcards
(21 cards)
Algoritmos ordenacion clasificacion:
-interno (memoria) / externo (fichero)
-natural tarda lo minimo si la entrada esta ordenada
-estable (mantiene orden relativo original za claves iguales)
Decir algoritmos Exchange sorts:(4)
Burbuja
Quicksort
Cocktail
Burbuja bi-direccional
Decir algoritmos Selection sorts:(2)
Seleccion
HeapSort
decir algoritmos Insertion sorts:(2)
Insercion/ShellSort
decir algoritmos Merge sorts
Merge Sort
Decir algoritmo distribution sorts
Bucket Sort o BinSort / Radix Sort
conjunto de reglas que aplicada sistemáticamente a unos datos de entrada apropiados, resuelven un problema en un numero finito de pasos elementales
Algoritmo
tecnicas de algoritmos
-Divide y venceras
-Voraces (opcion optima en cada paso) DIJKSTRA/A* PRIM/KRUSKAL
-Probalisticos (montecarlos/las vegas)
-Backtracking (explora arbol soluciones)
-Ramificacion y poda
-Programacion dinamica
BIG O NOTATION (cota superior asintotica)
Desplazando el numero mas grande que nos encontramos a base de comparaciones e intercambios entre elementos adyacentes
BURBUJA
0 (n2)
algoritmo de ordenacion
1.Busca el lugar que le corresponde a XI dentro del subarray que ya esta ordenado
2.desplaza a todos los elementos necesarios para hacerle hueco a XI
Insercion Directa
0 (n2)
algoritmo de ordenacion
1.intercambios de elementos >xi y elementos <xi
2.misma operativa xa cada subarray
QuickSort
0 (N LOG N)
Algoritmo de ordenacion
1.dividir la lista en sublistas hasta llegar al caso trivial
2.Mezclar dos sublistas para obtener una lista ordenada
MERGESORT
0 (N LOG N)
Algoritmo de ordenacion
Consiste en meter todos los elementos del array de datos en un monticulo y luego realizar N veces llamadas a eliminar_max ()
resultado decreciente
HeapSort o Monticulos
0 (N LOG N)
Algoritmo de ordenacion
1.buscas el minimo y lo pones en la 1 posicion
2. buscas el suguiente minimo a partir de la 1 posicion y la pones en la 2 pos etc.
Seleccion
0 (n2)
Algoritmo de ordenacion
Radix Sort
dos versiones:
LSD: usa el digito menos significativo
MSD:2 “ “ “ “ mas significativo
0(n-k)
Bucket Sort
BinSort
0 (n)
relacion de estructuras de datos
las cadenas son estructuras de datos contiguas
un array bidimensional es una matriz
una cola es una estructura FIFO
Saber el orden de BIG NOTATION
El algoritmo de Búsqueda binaria tiene como anotación big notation
0 (logn )
Algorithm-time Complexity
