Fundamentos de Algoritmos: Análisis de Complejidad, Notación Big-O, Búsqueda y Ordenamiento

Este artículo es una introducción completa a los fundamentos de algoritmos, incluyendo análisis de complejidad, notación Big-O, algoritmos de búsqueda y ordenamiento con ejemplos prácticos.

En Resumen

Los algoritmos son instrucciones paso a paso para resolver problemas. La notación Big-O describe su complejidad, los algoritmos de búsqueda localizan elementos y los algoritmos de ordenamiento organizan datos.

Descripción Técnica Compacta

Algoritmos son secuencias de instrucciones bien definidas y finitas para resolver un problema. Constituyen la base de la informática y desarrollo de software.

Análisis de complejidad:

• Complejidad temporal: Número de operaciones como función del tamaño de entrada
• Complejidad espacial: Espacio de memoria requerido
• Notación Big-O: Cota superior de la complejidad
• Mejor/Promedio/Peor caso: Distintos escenarios de tiempo de ejecución

Notación Big-O (principales):

• O(1): Tiempo constante
• O(log n): Tiempo logarítmico
• O(n): Tiempo lineal
• O(n log n): Tiempo linealítmico
• O(n²): Tiempo cuadrático
• O(2ⁿ): Tiempo exponencial

Puntos Clave para el Examen

• Algoritmos: Secuencias de instrucciones bien definidas para resolver problemas
• Notación Big-O: Descripción matemática de la complejidad
• Complejidad temporal: Número de operaciones dependiendo del tamaño de entrada
• Algoritmos de búsqueda: Linear Search (O(n)), Binary Search (O(log n))
• Algoritmos de ordenamiento: Bubble Sort (O(n²)), Quick Sort (O(n log n))
• Mejor/Peor/Promedio caso: Distintos escenarios de tiempo de ejecución
• Relevancia en la industria: Fundamento para desarrollo de software eficiente

Componentes Principales

1. Concepto de algoritmo: Entrada, procesamiento, salida
2. Análisis de complejidad: Requisitos de tiempo y espacio
3. Notación Big-O: Análisis asintótico
4. Algoritmos de búsqueda: Búsqueda lineal y binaria
5. Algoritmos de ordenamiento: Distintas estrategias de ordenamiento
6. Estructuras de datos: Arrays, listas, árboles, grafos
7. Recursión: Algoritmos autoinvocables
8. Divide y Conquista: Solución de problemas mediante división

Ejemplos Prácticos

1. Notación Big-O y Análisis de Complejidad

import java.util.*;

public class Komplexitaetsanalyse {
    
    // O(1) - Tiempo constante
    public int getFirstElement(int[] array) {
        if (array.length == 0) {
            throw new IllegalArgumentException("Array ist leer");
        }
        return array[0];  // Immer eine Operation
    }
    
    // O(n) - Tiempo lineal
    public int findMax(int[] array) {
        if (array.length == 0) {
            throw new IllegalArgumentException("Array ist leer");
        }
        
        int max = array[0];
        for (int i = 1; i < array.length; i++) {  // n Operationen
            if (array[i] > max) {
                max = array[i];
            }
        }
        return max;
    }
    
    // O(n²) - Tiempo cuadrático
    public void printPairs(int[] array) {
        for (int i = 0; i < array.length; i++) {        // n Schleifen
            for (int j = 0; j < array.length; j++) {    // n Schleifen
                System.out.println(array[i] + ", " + array[j]);
            }
        }
        // Gesamt: n * n = n² Operationen
    }
    
    // O(log n) - Tiempo logarítmico
    public int powerOfTwo(int n) {
        int result = 1;
        while (n > 0) {  // log₂(n) Schleifendurchläufe
            result *= 2;
            n /= 2;
        }
        return result;
    }
    
    // O(n log n) - Tiempo linealítmico
    public void mergeSort(int[] array) {
        if (array.length <= 1) {
            return;
        }
        
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        
        mergeSort(left);    // O(log n) Rekursionstiefe
        mergeSort(right);
        
        merge(array, left, right);  // O(n) für jeden Merge
    }
    
    private void merge(int[] result, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }
        
        while (i < left.length) {
            result[k++] = left[i++];
        }
        
        while (j < right.length) {
            result[k++] = right[j++];
        }
    }
    
    // O(2ⁿ) - Tiempo exponencial
    public int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);  // 2ⁿ Aufrufe
    }
    
    // Análisis de complejidad con medición de tiempo
    public void analyzeComplexity() {
        int[] sizes = {100, 1000, 10000, 100000};
        
        System.out.println("=== Análisis de Complejidad ===");
        System.out.println("Tamaño\tO(1)\tO(n)\tO(n²)\tO(log n)");
        
        for (int size : sizes) {
            int[] array = new int[size];
            
            // Llenar array con números aleatorios
            Random random = new Random();
            for (int i = 0; i < size; i++) {
                array[i] = random.nextInt(1000);
            }
            
            // Medir O(1)
            long start = System.nanoTime();
            getFirstElement(array);
            long o1Time = System.nanoTime() - start;
            
            // Medir O(n)
            start = System.nanoTime();
            findMax(array);
            long onTime = System.nanoTime() - start;
            
            // Medir O(n²) (solo para arrays pequeños)
            long on2Time = 0;
            if (size <= 1000) {
                start = System.nanoTime();
                printPairs(array);
                on2Time = System.nanoTime() - start;
            }
            
            // Medir O(log n)
            start = System.nanoTime();
            powerOfTwo(size);
            double olognTime = System.nanoTime() - start;
            
            System.out.printf("%d\t%d\t%d\t%d\t%.0f%n",
                             size, o1Time, onTime, on2Time, olognTime);
        }
    }
    
    public static void main(String[] args) {
        Komplexitaetsanalyse analyse = new Komplexitaetsanalyse();
        
        // Análisis de complejidad
        analyse.analyzeComplexity();
        
        // Demostración de Big-O
        System.out.println("\n=== Demostración de Big-O ===");
        demonstrateBigO();
        
        // Recursión vs Iteración
        System.out.println("\n=== Recursión vs Iteración ===");
        compareRecursionIteration();
    }
    
    private static void demonstrateBigO() {
        int n = 1000;
        Komplexitaetsanalyse demo = new Komplexitaetsanalyse();
        
        System.out.println("Demostración con n = " + n);
        
        // Ejemplo O(1)
        int[] array = {1, 2, 3, 4, 5};
        System.out.println("O(1) - Primer elemento: " + demo.getFirstElement(array));
        
        // Ejemplo O(n)
        int[] largeArray = new int[n];
        for (int i = 0; i < n; i++) {
            largeArray[i] = i;
        }
        System.out.println("O(n) - Máximo: " + demo.findMax(largeArray));
        
        // Ejemplo O(log n)
        System.out.println("O(log n) - 2^" + n + " = " + demo.powerOfTwo(n));
        
        // Ejemplo O(n log n)
        int[] sortArray = new int[100];
        Random random = new Random();
        for (int i = 0; i < 100; i++) {
            sortArray[i] = random.nextInt(1000);
        }
        System.out.println("O(n log n) - Merge Sort ejecutado");
        demo.mergeSort(sortArray);
        
        // Ejemplo O(n²) (array pequeño)
        int[] smallArray = {1, 2, 3, 4, 5};
        System.out.println("O(n²) - Todos los pares:");
        demo.printPairs(smallArray);
    }
    
    private static void compareRecursionIteration() {
        Komplexitaetsanalyse demo = new Komplexitaetsanalyse();
        int n = 30;
        
        System.out.println("Fibonacci n = " + n);
        
        // Versión recursiva (exponencial)
        long start = System.nanoTime();
        int recursiveResult = demo.fibonacci(n);
        long recursiveTime = System.nanoTime() - start;
        
        // Versión iterativa (lineal)
        start = System.nanoTime();
        int iterativeResult = fibonacciIterative(n);
        long iterativeTime = System.nanoTime() - start;
        
        System.out.println("Recursiva: " + recursiveResult + " (" + recursiveTime + "ns)");
        System.out.println("Iterativa: " + iterativeResult + " (" + iterativeTime + "ns)");
        System.out.println("Aceleración: " + (recursiveTime / iterativeTime) + "x");
    }
    
    private static int fibonacciIterative(int n) {
        if (n <= 1) return n;
        
        int a = 0, b = 1;
        for (int i = 2; i <= n; i++) {
            int temp = a + b;
            a = b;
            b = temp;
        }
        return b;
    }
}

2. Algoritmos de búsqueda

import java.util.*;

public class Suchalgorithmen {
    
    // Lineare Suche - O(n)
    public static int linearSearch(int[] array, int target) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == target) {
                return i;  // Element gefunden
            }
        }
        return -1;  // Element nicht gefunden
    }
    
    // Binäre Suche - O(log n) - Array muss sortiert sein
    public static int binarySearch(int[] sortedArray, int target) {
        int left = 0;
        int right = sortedArray.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (sortedArray[mid] == target) {
                return mid;  // Element gefunden
            } else if (sortedArray[mid] < target) {
                left = mid + 1;  // Rechts weitersuchen
            } else {
                right = mid - 1;  // Links weitersuchen
            }
        }
        
        return -1;  // Element nicht gefunden
    }
    
    // Interpolationssuche - O(log log n) im Durchschnitt
    // Funktioniert nur für gleichmäßig verteilte, sortierte Arrays
    public static int interpolationSearch(int[] sortedArray, int target) {
        int left = 0;
        int right = sortedArray.length - 1;
        
        while (left <= right && target >= sortedArray[left] && target <= sortedArray[right]) {
            if (left == right) {
                return sortedArray[left] == target ? left : -1;
            }
            
            // Interpolationsformel
            int pos = left + ((target - sortedArray[left]) * (right - left)) / 
                        (sortedArray[right] - sortedArray[left]);
            
            if (sortedArray[pos] == target) {
                return pos;
            } else if (sortedArray[pos] < target) {
                left = pos + 1;
            } else {
                right = pos - 1;
            }
        }
        
        return -1;
    }
    
    // Exponentielle Suche - O(log n) für unendlich große Arrays
    public static int exponentialSearch(int[] sortedArray, int target) {
        int n = sortedArray.length;
        
        if (sortedArray[0] == target) {
            return 0;
        }
        
        // Bereich finden, in dem das Element sein könnte
        int i = 1;
        while (i < n && sortedArray[i] <= target) {
            i = i * 2;
        }
        
        // Binäre Suche im gefundenen Bereich
        return binarySearchRange(sortedArray, i / 2, Math.min(i, n - 1), target);
    }
    
    private static int binarySearchRange(int[] array, int left, int right, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (array[mid] == target) {
                return mid;
            } else if (array[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
    
    // Jump Search - O(√n) für sortierte Arrays
    public static int jumpSearch(int[] sortedArray, int target) {
        int n = sortedArray.length;
        int step = (int) Math.sqrt(n);
        int prev = 0;
        
        // Block finden, in dem das Element sein könnte
        while (sortedArray[Math.min(step, n) - 1] < target) {
            prev = step;
            step += (int) Math.sqrt(n);
            if (prev >= n) {
                return -1;
            }
        }
        
        // Lineare Suche im Block
        while (sortedArray[prev] < target) {
            prev++;
            if (prev == Math.min(step, n)) {
                return -1;
            }
        }
        
        if (sortedArray[prev] == target) {
            return prev;
        }
        
        return -1;
    }
    
    // Performance-Vergleich der Suchalgorithmen
    public static void compareSearchAlgorithms() {
        Random random = new Random();
        int[] sizes = {1000, 10000, 100000, 1000000};
        
        System.out.println("=== Suchalgorithmen Performance-Vergleich ===");
        System.out.println("Größe\tLinear\tBinär\tInterpolation\tJump\tExponential");
        
        for (int size : sizes) {
            int[] array = new int[size];
            
            // Sortiertes Array erstellen
            for (int i = 0; i < size; i++) {
                array[i] = i;
            }
            
            // Zufälliges Ziel auswählen
            int target = random.nextInt(size);
            
            // Lineare Suche
            long start = System.nanoTime();
            int linearResult = linearSearch(array, target);
            long linearTime = System.nanoTime() - start;
            
            // Binäre Suche
            start = System.nanoTime();
            int binaryResult = binarySearch(array, target);
            long binaryTime = System.nanoTime() - start;
            
            // Interpolationssuche
            start = System.nanoTime();
            int interpolationResult = interpolationSearch(array, target);
            long interpolationTime = System.nanoTime() - start;
            
            // Jump Search
            start = System.nanoTime();
            int jumpResult = jumpSearch(array, target);
            long jumpTime = System.nanoTime() - start;
            
            // Exponentielle Suche
            start = System.nanoTime();
            int exponentialResult = exponentialSearch(array, target);
            long exponentialTime = System.nanoTime() - start;
            
            System.out.printf("%d\t%d\t%d\t%d\t\t%d\t%d%n",
                             size, linearTime, binaryTime, interpolationTime, jumpTime, exponentialTime);
            
            // Ergebnisse überprüfen
            assert linearResult == target;
            assert binaryResult == target;
            assert interpolationResult == target;
            assert jumpResult == target;
            assert exponentialResult == target;
        }
    }
    
    public static void main(String[] args) {
        // Test-Arrays erstellen
        int[] unsortedArray = {64, 34, 25, 12, 22, 11, 90, 88, 76, 50, 42};
        int[] sortedArray = {11, 12, 22, 25, 34, 42, 50, 64, 76, 88, 90};
        
        System.out.println("=== Suchalgorithmen Demo ===");
        
        // Lineare Suche
        int target = 25;
        int index = linearSearch(unsortedArray, target);
        System.out.println("Lineare Suche: " + target + " gefunden an Index " + index);
        
        // Binäre Suche
        index = binarySearch(sortedArray, target);
        System.out.println("Binäre Suche: " + target + " gefunden an Index " + index);
        
        // Interpolationssuche
        index = interpolationSearch(sortedArray, 76);
        System.out.println("Interpolationssuche: 76 gefunden an Index " + index);
        
        // Jump Search
        index = jumpSearch(sortedArray, 42);
        System.out.println("Jump Search: 42 gefunden an Index " + index);
        
        // Exponentielle Suche
        index = exponentialSearch(sortedArray, 88);
        System.out.println("Exponentielle Suche: 88 gefunden an Index " + index);
        
        // Performance-Vergleich
        compareSearchAlgorithms();
        
        // Suchalgorithmen-Eigenschaften
        printSearchAlgorithmProperties();
    }
    
    private static void printSearchAlgorithmProperties() {
        System.out.println("\n=== Suchalgorithmen Eigenschaften ===");
        
        String[][] algorithms = {
            {"Lineare Suche", "O(n)", "Unsortiert", "Einfach"},
            {"Binäre Suche", "O(log n)", "Sortiert", "Effizient"},
            {"Interpolationssuche", "O(log log n)", "Sortiert, gleichverteilt", "Sehr effizient"},
            {"Jump Search", "O(√n)", "Sortiert", "Gut für große Arrays"},
            {"Exponentielle Suche", "O(log n)", "Sortiert", "Unendliche Arrays"}
        };
        
        System.out.println("Algorithmus\t\tZeitkomplexität\tVoraussetzung\t\tBeschreibung");
        System.out.println("---------\t\t--------------\t--------------\t\t-----------");
        
        for (String[] algo : algorithms) {
            System.out.printf("%-20s\t%-15s\t%-20s\t%s%n", algo[0], algo[1], algo[2], algo[3]);
        }
    }
}

3. Algoritmos de ordenamiento

import java.util.*;

public class Sortieralgorithmen {
    
    // Bubble Sort - O(n²)
    public static void bubbleSort(int[] array) {
        int n = array.length;
        boolean swapped;
        
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            
            for (int j = 0; j < n - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    // Intercambiar elementos
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    swapped = true;
                }
            }
            
            // Si no hubo intercambios, el array está ordenado
            if (!swapped) {
                break;
            }
        }
    }
    
    // Selection Sort - O(n²)
    public static void selectionSort(int[] array) {
        int n = array.length;
        
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            
            // Encontrar el mínimo en la parte sin ordenar
            for (int j = i + 1; j < n; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            
            // Intercambiar el mínimo con el elemento actual
            if (minIndex != i) {
                int temp = array[i];
                array[i] = array[minIndex];
                array[minIndex] = temp;
            }
        }
    }
    
    // Insertion Sort - O(n²) worst case, O(n) best case
    public static void insertionSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int key = array[i];
            int j = i - 1;
            
            // Desplazar elementos hasta encontrar la posición correcta
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j--;
            }
            
            array[j + 1] = key;
        }
    }
    
    // Quick Sort - O(n log n) average, O(n²) worst case
    public static void quickSort(int[] array) {
        quickSortRecursive(array, 0, array.length - 1);
    }
    
    private static void quickSortRecursive(int[] array, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(array, low, high);
            
            quickSortRecursive(array, low, pivotIndex - 1);
            quickSortRecursive(array, pivotIndex + 1, high);
        }
    }
    
    private static int partition(int[] array, int low, int high) {
        int pivot = array[high];  // Usar el último elemento como pivote
        int i = (low - 1);  // Índice del elemento menor
        
        for (int j = low; j < high; j++) {
            if (array[j] < pivot) {
                i++;
                swap(array, i, j);
            }
        }
        
        swap(array, i + 1, high);
        return i + 1;
    }
    
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    
    // Merge Sort - O(n log n)
    public static void mergeSort(int[] array) {
        if (array.length <= 1) {
            return;
        }
        
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        
        mergeSort(left);
        mergeSort(right);
        
        merge(array, left, right);
    }
    
    private static void merge(int[] result, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }
        
        while (i < left.length) {
            result[k++] = left[i++];
        }
        
        while (j < right.length) {
            result[k++] = right[j++];
        }
    }
    
    // Heap Sort - O(n log n)
    public static void heapSort(int[] array) {
        int n = array.length;
        
        // Construir el max-heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(array, n, i);
        }
        
        // Extraer elementos del heap
        for (int i = n - 1; i > 0; i--) {
            swap(array, 0, i);
            heapify(array, i, 0);
        }
    }
    
    private static void heapify(int[] array, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        
        if (left < n && array[left] > array[largest]) {
            largest = left;
        }
        
        if (right < n && array[right] > array[largest]) {
            largest = right;
        }
        
        if (largest != i) {
            swap(array, i, largest);
            heapify(array, n, largest);
        }
    }
    
    // Comparación de rendimiento de algoritmos de ordenamiento
    public static void compareSortingAlgorithms() {
        Random random = new Random();
        int[] sizes = {1000, 5000, 10000, 20000};
        
        System.out.println("=== Comparación de rendimiento de algoritmos de ordenamiento ===");
        System.out.println("Tamaño\tBubble\tSelection\tInsertion\tQuick\tMerge\tHeap");
        
        for (int size : sizes) {
            // Crear array de prueba
            int[] originalArray = new int[size];
            for (int i = 0; i < size; i++) {
                originalArray[i] = random.nextInt(10000);
            }
            
            long[] times = new long[6];
            String[] names = {"Bubble", "Selection", "Insertion", "Quick", "Merge", "Heap"};
            
            // Bubble Sort
            int[] array = originalArray.clone();
            long start = System.nanoTime();
            bubbleSort(array);
            times[0] = System.nanoTime() - start;
            
            // Selection Sort
            array = originalArray.clone();
            start = System.nanoTime();
            selectionSort(array);
            times[1] = System.nanoTime() - start;
            
            // Insertion Sort
            array = originalArray.clone();
            start = System.nanoTime();
            insertionSort(array);
            times[2] = System.nanoTime() - start;
            
            // Quick Sort
            array = originalArray.clone();
            start = System.nanoTime();
            quickSort(array);
            times[3] = System.nanoTime() - start;
            
            // Merge Sort
            array = originalArray.clone();
            start = System.nanoTime();
            mergeSort(array);
            times[4] = System.nanoTime() - start;
            
            // Heap Sort
            array = originalArray.clone();
            start = System.nanoTime();
            heapSort(array);
            times[5] = System.nanoTime() - start;
            
            // Mostrar resultados
            System.out.printf("%d", size);
            for (long time : times) {
                System.out.printf("\t%d", time);
            }
            System.out.println();
        }
    }
    
    // Prueba de estabilidad
    public static void testStability() {
        System.out.println("\n=== Prueba de estabilidad ===");
        
        // Array con duplicados
        int[] array = {5, 2, 8, 5, 1, 9, 3, 5};
        
        System.out.println("Original: " + Arrays.toString(array));
        
        // Bubble Sort (estable)
        int[] bubbleArray = array.clone();
        bubbleSort(bubbleArray);
        System.out.println("Bubble Sort: " + Arrays.toString(bubbleArray));
        
        // Quick Sort (no estable)
        int[] quickArray = array.clone();
        quickSort(quickArray);
        System.out.println("Quick Sort: " + Arrays.toString(quickArray));
        
        // Merge Sort (estable)
        int[] mergeArray = array.clone();
        mergeSort(mergeArray);
        System.out.println("Merge Sort: " + Arrays.toString(mergeArray));
    }
    
    public static void main(String[] args) {
        // Array de prueba
        int[] array = {64, 34, 25, 12, 22, 11, 90, 88, 76, 50, 42};
        
        System.out.println("=== Demo de algoritmos de ordenamiento ===");
        
        // Bubble Sort
        int[] bubbleArray = array.clone();
        bubbleSort(bubbleArray);
        System.out.println("Bubble Sort: " + Arrays.toString(bubbleArray));
        
        // Selection Sort
        int[] selectionArray = array.clone();
        selectionSort(selectionArray);
        System.out.println("Selection Sort: " + Arrays.toString(selectionArray));
        
        // Insertion Sort
        int[] insertionArray = array.clone();
        insertionSort(insertionArray);
        System.out.println("Insertion Sort: " + Arrays.toString(insertionArray));
        
        // Quick Sort
        int[] quickArray = array.clone();
        quickSort(quickArray);
        System.out.println("Quick Sort: " + Arrays.toString(quickArray));
        
        // Merge Sort
        int[] mergeArray = array.clone();
        mergeSort(mergeArray);
        System.out.println("Merge Sort: " + Arrays.toString(mergeArray));
        
        // Heap Sort
        int[] heapArray = array.clone();
        heapSort(heapArray);
        System.out.println("Heap Sort: " + Arrays.toString(heapArray));
        
        // Comparación de rendimiento
        compareSortingAlgorithms();
        
        // Prueba de estabilidad
        testStability();
        
        // Propiedades de algoritmos de ordenamiento
        printSortingAlgorithmProperties();
    }
    
    private static void printSortingAlgorithmProperties() {
        System.out.println("\n=== Propiedades de algoritmos de ordenamiento ===");
        
        String[][] algorithms = {
            {"Bubble Sort", "O(n²)", "In-place", "Estable", "Simple"},
            {"Selection Sort", "O(n²)", "In-place", "No estable", "Simple"},
            {"Insertion Sort", "O(n²)", "In-place", "Estable", "Arrays pequeños"},
            {"Quick Sort", "O(n log n)", "In-place", "No estable", "Rápido"},
            {"Merge Sort", "O(n log n)", "Out-of-place", "Estable", "Confiable"},
            {"Heap Sort", "O(n log n)", "In-place", "No estable", "Garantizado"}
        };
        
        System.out.println("Algoritmo\t\tComplejidad de tiempo\tEspacio\t\tEstabilidad\tDescripción");
        System.out.println("---------\t\t---------------------\t-------\t\t-----------\t-----------");
        
        for (String[] algo : algorithms) {
            System.out.printf("%-20s\t%-20s\t%-15s\t%-15s\t%s%n", algo[0], algo[1], algo[2], algo[3], algo[4]);
        }
    }
}

Resumen de Big-O

Complejidad	Descripción	Ejemplo	Crecimiento
O(1)	Tiempo constante	Acceso a array	1
O(log n)	Logarítmica	Búsqueda binaria	log₂(n)
O(n)	Lineal	Búsqueda lineal	n
O(n log n)	Lineal-logarítmica	Merge Sort	n·log(n)
O(n²)	Cuadrática	Bubble Sort	n²
O(2ⁿ)	Exponencial	Fibonacci recursivo	2ⁿ

Comparativa de Algoritmos de Búsqueda

Algoritmo	Complejidad Temporal	Requisito	Mejor Caso
Linear Search	O(n)	Ninguno	Arrays pequeños sin ordenar
Binary Search	O(log n)	Ordenado	Arrays grandes ordenados
Interpolation	O(log log n)	Ordenado, distribución uniforme	Datos numéricos
Jump Search	O(√n)	Ordenado	Arrays grandes con tamaño de salto
Exponential	O(log n)	Ordenado	Arrays infinitos

Comparativa de Algoritmos de Ordenamiento

Algoritmo	Complejidad Temporal	Complejidad Espacial	Estable	In-place
Bubble Sort	O(n²)	O(1)	Sí	Sí
Selection Sort	O(n²)	O(1)	No	Sí
Insertion Sort	O(n²)	O(1)	Sí	Sí
Quick Sort	O(n log n)	O(log n)	No	Sí
Merge Sort	O(n log n)	O(n)	Sí	No
Heap Sort	O(n log n)	O(1)	No	Sí

Principios de Diseño de Algoritmos

Divide and Conquer

1. Dividir: descomponer el problema en subproblemas más pequeños
2. Conquistar: resolver los subproblemas recursivamente
3. Combinar: unir las soluciones

Ejemplos: Quick Sort, Merge Sort, Binary Search

Algoritmos Greedy

1. Decisiones localmente óptimas
2. Esperanza de optimalidad global

Ejemplos: Dijkstra, Kruskal, Huffman Coding

Programación Dinámica

1. Estructura óptima: subproblemas superpuestos
2. Memoization: guardar resultados intermedios

Ejemplos: Fibonacci, Knapsack Problem

Optimización de Rendimiento

Intercambio Espacio-Tiempo

// Intercambiar memoria por velocidad
public class FibonacciMemoization {
    private static Map<Integer, Long> memo = new HashMap<>();
    
    public static long fibonacci(int n) {
        if (n <= 1) return n;
        
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        
        long result = fibonacci(n - 1) + fibonacci(n - 2);
        memo.put(n, result);
        return result;
    }
}

Terminación Temprana

// Búsqueda lineal optimizada con centinela
public static int optimizedLinearSearch(int[] array, int target) {
    int n = array.length;
    
    // Último elemento como centinela
    if (array[n - 1] == target) {
        return n - 1;
    }
    
    // Reemplazar último elemento por el objetivo
    int last = array[n - 1];
    array[n - 1] = target;
    
    int i = 0;
    while (array[i] != target) {
        i++;
    }
    
    // Restaurar valor original
    array[n - 1] = last;
    
    return i < n - 1 ? i : -1;
}

Ventajas e Inconvenientes

Ventajas del Análisis de Algoritmos

• Predicción de Rendimiento: estimar el tiempo de ejecución
• Selección de Algoritmo: elegir el enfoque adecuado
• Optimización: identificar cuellos de botella
• Escalabilidad: entender el comportamiento de crecimiento

Inconvenientes

• Suposiciones Teóricas: ignora constantes
• Diferencias Prácticas: efectos del hardware
• Complejidad: análisis matemático costoso
• Over-Engineering: optimización prematura

Preguntas Frecuentes de Examen

1. ¿Cuál es la diferencia entre Best Case, Average Case y Worst Case? Best Case: ruta óptima, Average Case: desempeño esperado, Worst Case: ruta más desfavorable.

2. ¿Por qué Binary Search es O(log n) y no O(n)? Al dividir a la mitad el rango de búsqueda en cada paso, la búsqueda se acelera logarítmicamente.

3. ¿Cuándo usar Insertion Sort en lugar de Quick Sort? Con arrays pequeños o datos casi ordenados, donde Insertion Sort alcanza O(n).

4. ¿Qué significa In-place en algoritmos de ordenamiento? El algoritmo ordena sin usar espacio adicional (O(1) de espacio).

Fuentes Principales

1. https://en.wikipedia.org/wiki/Big_O_notation
2. https://www.geeksforgeeks.org/fundamentals-of-algorithms/
3. https://mitpress.mit.edu/books/introduction-algorithms