ALGORITMOS: ¿Qué es un algoritmo?
Un conjunto de instrucciones claras y ordenadas
que se siguen paso a paso
para resolver un problema o hacer una tarea
en un tiempo finito ‼️‼️‼️‼️
a partir de unos datos de entrada
ALGORITMOS: ¿Cuáles son los métodos para representar o resolver algoritmos?Dos Formales
Pandillas
Sureñas Fenomenales
Diagrama de flujo: Representación gráfica con símbolos y flechasPseudocódigo: Descripción en lenguaje informal estructuradoSistemas formales: Uso de expresiones matemáticas lógicas
ANÁLISIS Y DISEÑO: ¿Qué es el análisis y diseño para la resolución de algoritmos ?
Análisis: Estudiar la eficiencia del algoritmo
(cuántotiempotarda y cuántamemoriausa)Diseño: Crear una solución paso a paso que sea clara, eficiente y correcta
ANÁLISIS Y DISEÑO: ¿Cuáles son las principales TÉCNICAS DE DISEÑO de algoritmos?Don Víctor Planta Bambú Rojo Pronto
Divide y vencerás: Divide el problema en subproblemas más pequeños (merge sort)Voraces: Elige la mejor opción en cada pasoProbabilísticas: Usan azar (ej. Montecarlo, Las Vegas)Backtracking: Explora todas las opciones posibles como un árbol pudiendo retroceder para elegir de nuevoRamificación y poda: Como backtracking, pero eliminando ramas inútilesProgramación dinámica: Resuelve subproblemas y combina soluciones
(bottom-up o top-down con memorización)
ANÁLISIS Y DISEÑO: ¿Ejemplo de la técnica divide y vencerás?
Problema: Ordenar una lista de números
Algoritmo: Merge Sort
Pasos:
- Dividir la lista en mitades hasta que quede una sola posición
- Ordenar cada mitad por separado
- Combinar (merge) las mitades ordenadas
ANÁLISIS Y DISEÑO: ¿Ejemplo de la técnica voraz? Tipo de algoritmo.
Problema: Encontrar el camino más corto entre dos nodos
Algoritmo: Dijkstra
Requiere: Un grafo con pesos NO negativos
Pasos:
- Empieza desde el nodo inicial
- En cada paso, elige el nodo más cercano no visitado
- Actualiza las distancias más cortas conocidas
- Repite hasta llegar al destino
ANÁLISIS Y DISEÑO: ¿Ejemplo de la técnica probabilística? Números primos. Tipo de algoritmo.
Problema: Verificar si un número es primo
Algoritmo: Miller-Rabin (tipo Monte Carlo)
Características:
- Usa números aleatorios para hacer pruebas
- Puede dar una respuesta incorrecta con muy baja probabilidad
- Es rápido y útil para números muy grandes
ANÁLISIS Y DISEÑO: ¿Ejemplo de la técnica backtracking?
Problema: Resolver un Sudoku
Algoritmo: Búsqueda con retroceso (backtracking)
Método: Tipo prueba y error
Otros ejemplos clásicos:
- El problema del caballo
- Las ocho reinas (extensible a n²)
Pasos:
- Rellenar una celda vacía con un número posible
- Avanzar a la siguiente celda
- Si no hay opción válida, retroceder (backtrack) y probar otra
- Repetir hasta completar la solución válida
ANÁLISIS Y DISEÑO: ¿Qué es la técnica ramificación y poda? ¿En que técnica se basa?
- Técnica basada en
backtracking(si no funciona, regresamos) - Explora un árbol de soluciones
Ramificación: generar todas las posibles opciones desde un nodoPoda: eliminar ramas que no pueden mejorar la solución actual- Reduce el número de caminos explorados
- Muy útil en problemas de optimización (como el del viajante)
ANÁLISIS Y DISEÑO: ¿Qué es la técnica programación dinámica?
- Resuelve problemas dividiéndolos en
subproblemas más pequeños Guarda las solucionesde los subproblemas para no repetir cálculos (MEMOIZACION)- Usa enfoques bottom-up o top-down con memorización
- Ideal cuando el problema tiene subproblemas solapados y estructura óptima
Ejemplo clásico:
- Problema de la mochila
- Fibonacci (más eficiente que con recursión simple)
ANÁLISIS Y DISEÑO: ¿Qué es la notación Big O? ¿De fine el mejor 💚 o el peor 🔴 de los casos?
- Es una forma de expresar la ✨`eficiencia‘✨ de un algoritmo
- Mide cuanto crece el
tiempo o memoriasegún el tamaño de los datos - Describe el
peor🔴 caso en la mayoría de los casos - Permite comparar algoritmos de forma abstracta
Ejemplos:
- O(1) → constante
- O(log n) → logarítmico (búsqueda binaria)
- O(n) → lineal
- O(n²) → cuadrático
- O(cⁿ) → exponencial (ej. backtracking en problemas complejos)
- O(n^f(n)) → subexponencial (f(n) < n, más lento que polinómico)
- O(nⁿ) → superexponencial (crece muchísimo más rápido que exponencial)
ANÁLISIS Y DISEÑO: ¿Qué es la complejidad logarítmica?
- Es una complejidad donde el problema
se reduce a la mitaden cada paso - Se representa como O(log n)
- Es muy eficiente con grandes cantidades de datos
- Ejemplo: búsqueda binaria en listas ordenadas
ALGORTIMOS DE ORDENACIÓN: ¿Clasificación general de los algoritmos de ordenación?Isabel Escribe Notas Elegantes Diarias
Interno (memoria)
- Ordena cuando todos los datos caben en RAM.
🧠 Ej: ordenar 100 números en una lista en Python en memoria.
Externo (fichero)
- Ordena cuando los datos no caben en RAM y se trabaja con disco.
🧠 Ej: ordenar un archivo enorme de 10 GB en un servidor.
Natural
- Se aprovecha si la ENTRADA ya está ordenada (parcial o totalmente).
🧠 Ej: lista [1,2,3,7,8] se ordena muy rápido porque ya casi está en orden.
Estable
- Mantiene el orden original entre elementos con valores iguales.
🧠 Ej: [A1, A2, B] → tras ordenar por letra sigue [A1, A2, B].
Directa
- Ordena comparando los elementos uno a uno desde el principio hasta el final (método básico y lento).
🧠 Ej: el burbujeo: [3,2,1] → compara 3 y 2 → [2,3,1] → compara 3 y 1 → [2,1,3]…
ALGORTIMOS DE ORDENACIÓN: ¿Métodos de ordenación más comunes?El señor inspector me decepciona
🔄 Exchange sort: comparan elementos y los intercambian si están fuera de orden.
🎯 Selection sort: buscan el elemento correcto (mínimo/máximo) y lo colocan en su posición final.
📝 Insertion sort: insertan cada nuevo elemento en su lugar dentro de la parte ya ordenada.
🪢 Merge sort: dividen la lista en partes pequeñas, las ordenan y luego las juntan en orden.
📦 Distribution sort: agrupan los elementos en contenedores/cubetas según reglas y luego los reordenan.
ALGORTIMOS DE ORDENACIÓN: ¿Cómo funciona el algoritmo Burbuja sort?
- Pertenece a la categoría
exchange sort
El algoritmoBubble Sortordena una lista comparando e intercambiando pares de elementos adyacentes desde laizquierda, en múltiples pasadas. En cada pasada, el mayor valor se mueve (como una burbuja) hacia el final de la lista.
🔹 Siempre empieza desde el principio en cada pasada
🔹 Continúa hasta que ya no se hagan intercambios
🧠 Ejemplo con [5, 1, 4]:
1ª pasada → [1, 5, 4] → [1, 4, 5]
2ª pasada → compara desde el principio, ya está ordenado
📈 Eficiencia:
- Mejor caso (lista ya ordenada): O(n)
- Peor caso (lista invertida): O(n²)”
ALGORTIMOS DE ORDENACIÓN: ¿Cómo funciona el algoritmo Quicksort? ¿A que categoría pertenece?
- Pertenece a la categoría
exchange sort - Elige un elemento como pivote
- Divide la lista en dos: menores y mayores que el pivote
- Ordena recursivamente cada sublista
- Muy eficiente en promedio: O(n log n)
Peor caso: O(n²)(si el pivote es muy mal elegido)
ALGORTIMOS DE ORDENACIÓN: ¿Cómo funcionan los algoritmos inserción e inserción binaria?
- Ambos pertenecen a la categoría
insertion sort - Recorren la lista de izquierda a derecha
- Cada nuevo elemento se
insertaen suposicióncorrecta respecto a los anteriores
Inserción directa:
- Compara hacia atrás uno a uno hasta encontrar su lugar
- Ejemplo: en [2, 4, 7], insertamos 3
- Compara con 7 → luego con 4 → ve que 3 < 4 y 3 > 2
- Inserta antes de 2
- Se empieza a comparar desde el último dato porque la lista ya está ordenada
Inserción binaria: 🧠🧠 La búsqueda binaria consiste en encontrar un valor en una lista ordenada dividiéndola repetidamente por la mitad hasta localizarlo o descartarlo
- Usa búsqueda binaria para encontrar la posición correcta
- En cada paso compara con el pivote (el elemento central del rango)
- Luego desplaza los elementos para insertar
- Ejemplo: en [2, 4, 7], insertamos 3
- Pivote = 4 → 3 < 4, va a la izquierda
- Pivote = 2 (pivote de los que están a la izquierda del 4) → 3 > 2, posición final: entre 2 y 4
- Inserta entre 2 y 4`
Complejidad:O(n²)(menoscomparacionesen binaria, pero igual desplazamientos)
ALGORTIMOS DE ORDENACIÓN: ¿Cómo funciona el algoritmo Merge Sort?
- Pertenece a la categoría
divide y vencerás - Divide recursivamente la lista en
MITADES(❌⚠️ NO comobucket sortque lo hace enCATEGORÍAS) hasta que queden elementos individuales - Luego
fusiona(merge) esas mitades ordenándolas
Pasos:
- Dividir: separar la lista en mitades
- Ordenar cada mitad de forma recursiva
- Combinar ambas mitades en orden
Complejidad:O(n log n)(eficiente incluso en el peor caso)
ALGORTIMOS DE ORDENACIÓN: ¿Cómo funciona el algoritmo HeapSort?
- Pertenece a la categoría
selection sort - Usa una estructura llamada
montículo(heap) para ordenar - En un
montículo, elvalor máximosiempre está en la raíz
Pasos:
- Construir un montículo máximo con todos los elementos
- Extraer el valor de la raíz (el mayor) y colocarlo al final
- Reorganizar el montículo (y subir el nuevo montículo)
- Repetir hasta vaciarlo
Complejidad:O(n log n)- No necesita espacio adicional
ALGORTIMOS DE ORDENACIÓN: ¿Cómo funciona el algoritmo de selección? ¿Qué es el candidato prometedor?
- Pertenece a la categoría
selection sort - Busca en cada pasada el
candidato prometedor(el menor de los no ordenados) - Lo intercambia con la
posiciónactual
Pasos:
- Recorre toda la lista y selecciona el valor más pequeño
- Lo coloca en la primera posición
- Repite el proceso con el resto de la lista
Complejidad:O(n²)(aunque hace menos intercambios que burbuja)
ALGORTIMOS DE ORDENACIÓN: ¿Cómo funciona el algoritmo Radix Sort? ¿Cuáles son sus dos variantes?
- Pertenece a la categoría
distribution sort - Ordena los elementos
dígito a dígito, empezando por unaposiciónconcreta - ❌ No compara elementos
enteroscomo otros algoritmos ⭐️ - Utiliza almacenamiento adicional como
colasobucketpara agrupar los datos temporalmente ⭐️
Variantes:
- LSD (Least Significant Digit): ordena primero por el dígito menos significativo (derecha)
- MSD (Most Significant Digit): comienza por el dígito más significativo (izquierda)
Aspectos clave (más sencillo):
- Cuantos más dígitos tengan los números, más tiempo llevará ordenarlos
- El algoritmo hace una pasada por cada dígito
- Funciona muy bien si todos los números tienen la misma cantidad de dígitos
Complejidad:O(n·k)
(siendonlos elementos ykla cantidad dedígitospor número)
🧠 Ejemplo con [170, 45, 75]
Paso 1 – Unidades (1s):
Ordenamos según el último dígito:
[170, 75, 45] → termina en 0, 5, 5 → orden: [170, 45, 75]
Paso 2 – Decenas (10s):
Dígitos: 7, 4, 7 → orden: [45, 170, 75]
Paso 3 – Centenas (100s):
Dígitos: 0, 1, 0 → orden: [45, 75, 170]
📌 Resultado final: [45, 75, 170]
ALGORTIMOS DE ORDENACIÓN: ¿Cómo funcionan los algoritmos Bucket Sort y Bin Sort?
- Pertenecen a la categoría
distribution sort - Dividen los datos en varios grupos llamados
buckets(cubos o contenedores) - Cada
bucketagrupa elementos que están dentro de unmismo rango - Luego se ordena cada
bucket(usando otro algoritmo comoinserción)
Características clave:
- Muy eficiente si los datos están uniformemente distribuidos
- Ideal para ordenar números en un rango conocido (por ejemplo, entre 0 y 100)
- Bin Sort es una variante muy similar, especialmente usada para enteros
Complejidadpromedio:O(n + k)
(nelementos,knúmero debuckets)- En el peor caso: puede llegar a
O(n²)si los datos caen todos en un solobucket
BUCLES ¿Qué es un bucle? ¿Cuándo para?
Es una estructura que permite repetir una serie de instrucciones varias veces ⭐️⭐️⭐️ hasta que se cumpla una condición
BUCLES ¿Qué es un bucle for? ¿Cuántas partes tiene? ¿Cuando es adecuado usarlas?
Es un bucle que se repite un número exacto de veces
Tiene 3 partes:
- Inicio: se define una variable (por ejemplo, i = 1)
- Condición: se repite mientras se cumpla (por ejemplo, i ≤ 5)
- Incremento: cambia el valor en cada vuelta (por ejemplo, i++)
Se usa cuando sabemos cuántas veces queremos repetir algo
En este ejemplo, se repite 5 veces porque empieza en 1 y termina cuando i llega a 5
