BII Tema 3 Secc2 Algoritmos Flashcards
Complejidad temporal
El tiempo de cómputo (que tarda) para ejecutar un programa
Big O anotation
Es la curva que representa la complejidad temporal.
Cota superior (asíntota) respecto del tiempo que tarda un algoritmo.
Complejidad espacial
Si usa mucha o poca memoria. Para saber los recursos que necesitamos
Big O anotation.
De mejor comportamiento a peor
O (1) orden constante
O(log log N)
O(log N)
O(N)
O(N*log N)
O(N^2)
O(n^3)
O(C^n)
O(N!)
O(n^n)
Algoritmos ordenación
Clasificación según donde lo ordena
Externo - en disco (fichero)
Interno - en memoria
Algoritmos ordenación
Clasificación según tiempo que tarda
Naturales -minimo posible si está ordenado
No naturales -minimo posible si está inversamente ordenado
Familias algoritmos
Exchange sort
Basados en Intercambio de datos
Burbuja
Quick Sort
Cocktail o burbuja bidireccional
Familias algoritmos
Selección sort
Basados en cual es el siguiente elemento
Selección
Heapsort
Familias algoritmos
Inserción sort
Basado en el siguiente elemento donde la va a colocar
Inserccion
Shellsort
Familia algoritmo
Merge sort
Basado en mezcla
Merge sort
Familias algoritmos
Distribution sort
Distribuye, hace una clasificación. Necesita espacio adicional
Bucket Sort (bin sort)
Radix sort
Algoritmo burbuja (Bubble Sort)
Complejidad temporal.
Complejidad espacial
Clasificación
Complejidad temporal
Caso mejor - O (N) - si están ordenados los datos
Caso medio y peor - O (n^2)
Complejidad espacial
O (1)
Clasificación
Intercambio, natural
Descripción: deja el más grande el último y la segunda vuelta ya tiene n-1 elementos y repite. Se puede hacer creciente y decreciente
Algoritmo inserción directa
Complejidad temporal y espacial
Clasificacion
Complejidad temporal
caso mejor - O (N)
Caso peor y medio - O(n^2)
Complejidad espacial
O (1)
Clasificación
Insercion
Descripción: busca de uno a uno
Algoritmo quicksort
Complejidad temporal y espacial
Clasificacion
Complejidad temporal
Caso medio y mejor- O( N log(N))
Caso peor- O (n^2)
Complejidad espacial
O (log(N))
Clasificación
Divide y vence. Intercambio. No estable.
Descripción :Elección pivote pequeños a un lado y grandes al otro
Algoritmo merge sort
Complejidad temporal y espacial
Clasificacion
Complejidad temporal
Todos los casos O(log N)
Clasificación espacial
O(N)
Clasificación
Mezcla
Descripción:divide la lista en sublistas hasta llegar a un caso trivial. Recursividad. Y luego mezcla la sublista
Algoritmo heapsort monticulo
Complejidad temporal y espacial
Complejidad temporal
Todos los casos O (log (N)) estable
Complejidad espacial
O(1)
Descripción: encontrar el mayor y es la raíz. Y ya reconstruye como un monticulo
Algoritmo seleccion
Complejidad temporal y espacial
Clasificacion
Complejidad temporal
O (n^2)
Complejidad espacial
O(1)
Descripción: busca el mínimo y lo pone el primero. Y así sucesivamente
Algoritmo radix sort
Complejidad temporal y espacial
Clasificacion
Complejidad temporal
O (N*k) ; k=n° dígitos
Complejidad espacial
O(N+k)
Clasificación
Distribución
2 versiones LSD ( empieza dígito menos representativo, unidades derecha) y MSD (Empieza por el más representativo, el de la izquierda)
Lee dígito a digito
Algoritmo Bin Sort o bucket sort
Complejidad temporal y espacial
Clasificacion
Complejidad temporal
caso mejor O(N) nota este encontré yoO (N+k) ; k= n° casilleros (buckets)
Peor caso o(n^2)
Complejidad espacial
O(N)
Clasificación
Distribucion. Ordenaciones parciales. En casillero por rango de valores
Diseño: técnicas
divide y vence
Troceas el problema en 2 subproblema, y el subproblema en otros 2. Así puedes llegar a un caso trivial o caso base que ya sepas resolver
Diseño : tecnicas
Programación dinamica
bottom Up / top down + memoizacion
Lo contrario que divide y vence.
Una vez tienes el camino para resolver el problema. A partir de un caso pequeño óptimo, va añadiendo cada vez problemas más grandes
Se suele usar después de divide y vence
Diseño técnicas
Voraces
En cada paso intenta deducir la solución más óptima
Dijkstra, prim/kruskal
Diseño técnicas
Probabilisticos
Introducen una variable aleatoria para resolver el problema
Ejemplo :Montecarlo las vegas, sherwood
Diseño técnicas
Backtracking ( vuelta atrás)
Explora el árbol con todas las posibles soluciones ñ. Lo usas cuando no tienes ninguna estrategia. Tardan mucho
Diseño : técnicas
Ramificación y poda
Va de la mano de backtracking.
Se da cuenta que por ahí ya pasaste y ha probado todas las posibilidades y por ahí no va la solución, lo desecha ( poda)
