Semana01 - davidethc/AlgoritmosJava GitHub Wiki
Basado en Brassard & Bratley, 2006
Un algoritmo es una secuencia finita de pasos bien definidos que resuelven un problema específico. Debe ser claro, preciso y determinístico.
- Finito (termina en algún momento).
- Preciso (cada paso es claro).
- Efectivo (resuelve el problema).
El análisis busca determinar la eficiencia de un algoritmo en términos de tiempo y espacio. Evaluar esta eficiencia permite comparar soluciones y tomar decisiones informadas sobre cuál utilizar.
Las siguientes notaciones describen el comportamiento de un algoritmo a medida que crece el tamaño de la entrada:
- Big O (O): Representa el peor caso.
- Theta (Θ): Representa el caso promedio.
- Omega (Ω): Representa el mejor caso.
Los algoritmos manipulan datos a través de estructuras de datos, que permiten organizar la información eficientemente.
- Arrays: Colección de elementos en posiciones contiguas.
- Listas: Elementos conectados mediante referencias (listas enlazadas).
- Pilas (Stacks): Acceso LIFO (último en entrar, primero en salir).
- Colas (Queues): Acceso FIFO (primero en entrar, primero en salir).
import java.util.Stack;
public class EstructuraDemo {
public static void main(String[] args) {
// Array simple
int[] numeros = {10, 20, 30};
System.out.println("Array:");
for (int num : numeros) {
System.out.println(num);
}
// Pila (Stack)
Stack<String> pila = new Stack<>();
pila.push("A");
pila.push("B");
pila.push("C");
System.out.println("\nPila:");
while (!pila.isEmpty()) {
System.out.println(pila.pop());
}
}
}
## Ejemplo en Java: Comparación de algoritmos
```java
public class AnalisisDemo {
public static void main(String[] args) {
int n = 1000;
// Algoritmo O(n)
long start = System.nanoTime();
for (int i = 0; i < n; i++) {
// Operación constante
}
long end = System.nanoTime();
System.out.println("Tiempo O(n): " + (end - start) + " ns");
// Algoritmo O(n^2)
start = System.nanoTime();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// Operación constante
}
}
end = System.nanoTime();
System.out.println("Tiempo O(n^2): " + (end - start) + " ns");
}
}
# Diseño de Algoritmos
Existen distintas técnicas clásicas para diseñar algoritmos eficientes:
- **División y conquista**: Se divide el problema en subproblemas más pequeños, se resuelven de forma recursiva y se combinan los resultados.
- **Programación dinámica**: Se almacenan resultados intermedios para evitar cálculos repetidos (memorización).
- **Algoritmos codiciosos (greedy)**: Se elige siempre la mejor opción local con la esperanza de alcanzar una solución global óptima.
---
## Ejemplo Java: División y conquista (Búsqueda binaria)
```java
public class Binaria {
public static int busquedaBinaria(int[] arr, int clave) {
int inicio = 0, fin = arr.length - 1;
while (inicio <= fin) {
int medio = (inicio + fin) / 2;
if (arr[medio] == clave) return medio;
if (arr[medio] < clave) inicio = medio + 1;
else fin = medio - 1;
}
return -1; // No encontrado
}
public static void main(String[] args) {
int[] datos = {1, 3, 5, 7, 9, 11};
int indice = busquedaBinaria(datos, 7);
System.out.println("Índice encontrado: " + indice);
}
}Este algoritmo tiene complejidad O(log n) gracias a su enfoque de división y conquista, lo que lo hace eficiente para buscar elementos en arreglos ordenados.
Este primer capítulo sienta las bases del análisis y diseño de algoritmos. A lo largo de tu formación aprenderás a:
- Identificar estructuras de datos adecuadas.
- Analizar la eficiencia temporal y espacial.
- Elegir las mejores estrategias de diseño para resolver problemas reales.
Estos conocimientos son fundamentales para desarrollar software eficiente, escalable y mantenible.