ALGORITMOS CON EJEMPLOS EN JAVASCRIPT: GUÍA ÚTIL PARA PROGRAMADORES

Algoritmos fundamentales con ejemplos en JavaScript

En el desarrollo de software, la creación de algoritmos eficientes es una habilidad esencial para cualquier programador. Los algoritmos con ejemplos en JavaScript permiten entender y aplicar conceptos fundamentales que optimizan la resolución de problemas. En esta guía completa, exploraremos varios algoritmos clave, explicando su funcionamiento y mostrando implementaciones prácticas en JavaScript.

Búsqueda binaria: optimizando la búsqueda en listas ordenadas

La búsqueda binaria es una técnica que divide repetidamente una lista ordenada para localizar un elemento específico de manera eficiente. A diferencia de la búsqueda lineal, que examina cada elemento secuencialmente, la búsqueda binaria reduce el espacio de búsqueda a la mitad en cada paso, logrando encontrar un elemento en una lista de un millón en apenas veinte iteraciones.

Para ilustrar, considere una lista ordenada de números del 1 al 10 y la necesidad de encontrar el número 5. El algoritmo compara el elemento central con el valor buscado y decide si continuar la búsqueda en la mitad izquierda o derecha, descartando la otra mitad. Este proceso se repite hasta encontrar el elemento o agotar la lista.

La implementación en JavaScript es sencilla y eficiente:

let lista = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

function busquedaBinaria(arr, x) {
    let inicio = 0,
        fin = arr.length - 1;

    while (inicio <= fin) {
        let medio = Math.floor((inicio + fin) / 2);

        if (arr[medio] === x) return true;
        else if (arr[medio] < x) inicio = medio + 1;
        else fin = medio - 1;
    }
    return false;
}

Para probar la función:

let numeroBuscado = 5;
if (busquedaBinaria(lista, numeroBuscado)) console.log("Número encontrado");
else console.log("Número no encontrado");

La búsqueda binaria es una técnica imprescindible para programadores que buscan optimizar sus procesos de búsqueda en estructuras ordenadas.

Algoritmos de recorrido en grafos: DFS y BFS

Los algoritmos de recorrido de grafos son fundamentales para explorar estructuras que representan relaciones complejas, como redes sociales, mapas o bases de datos. Comprender estos algoritmos es esencial para programadores que trabajan con estructuras de datos avanzadas.

Recorrido en profundidad (DFS)

El recorrido en profundidad (Depth-First Search, DFS) explora un grafo de manera recursiva o utilizando una pila, visitando nodos adyacentes antes de retroceder. Comienza en un nodo raíz y se adentra en cada rama hasta que no quedan nodos por visitar.

La implementación en JavaScript con una pila es la siguiente:

function DFS(graph, startNode) {
    let visited = [];
    let stack = [startNode];

    while (stack.length > 0) {
        let currentNode = stack.pop();

        if (!visited.includes(currentNode)) {
            visited.push(currentNode);

            let adjacentNodes = graph[currentNode];

            for (let i = 0; i < adjacentNodes.length; i++) {
                stack.push(adjacentNodes[i]);
            }
        }
    }

    return visited;
}

Recorrido en anchura (BFS)

El recorrido en anchura (Breadth-First Search, BFS) explora el grafo capa por capa, visitando todos los nodos adyacentes a un nodo antes de avanzar a los siguientes niveles. Utiliza una cola para gestionar el orden de visita.

Su implementación en JavaScript es:

function BFS(graph, startNode) {
    let visited = [];
    let queue = [startNode];

    while (queue.length > 0) {
        let currentNode = queue.shift();

        if (!visited.includes(currentNode)) {
            visited.push(currentNode);

            let adjacentNodes = graph[currentNode];

            for (let i = 0; i < adjacentNodes.length; i++) {
                queue.push(adjacentNodes[i]);
            }
        }
    }

    return visited;
}

Estos algoritmos son la base para resolver problemas complejos en grafos y son ampliamente utilizados en diversas aplicaciones de programación.

Complejidad temporal: entendiendo el rendimiento de los algoritmos

La complejidad temporal es un concepto clave para programadores que desean evaluar cuánto tiempo tomará un algoritmo para completar su tarea en función del tamaño de la entrada. Este conocimiento es vital para diseñar aplicaciones eficientes y escalables, especialmente en entornos de alta demanda o tiempo real.

Notación Big O: una medida estándar

La notación Big O describe cómo varía el tiempo de ejecución de un algoritmo a medida que crece la entrada. Se enfoca en el comportamiento asintótico, ignorando constantes y términos menores para ofrecer una visión general del rendimiento.

Ejemplos prácticos en JavaScript

O(1) - Tiempo constante

function obtenerPrimerElemento(arr) {
    return arr[0];
}

Esta función siempre retorna el primer elemento, sin importar el tamaño del arreglo.

O(n) - Tiempo lineal

function sumarElementos(arr) {
    let suma = 0;
    for (let i = 0; i < arr.length; i++) {
        suma += arr[i];
    }
    return suma;
}

El tiempo de ejecución crece linealmente con el tamaño del arreglo.

O(n²) - Tiempo cuadrático

function imprimirPares(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            console.log(arr[i], arr[j]);
        }
    }
}

Este algoritmo realiza operaciones para cada par de elementos, aumentando el tiempo de ejecución exponencialmente.

Comprender la complejidad temporal de nuestros algoritmos permite tomar decisiones informadas para optimizar el rendimiento y garantizar la escalabilidad de las aplicaciones.

Complejidad espacial: optimizando el uso de memoria en algoritmos

Además del tiempo de ejecución, la complejidad espacial es crucial para evaluar cuánta memoria consume un algoritmo durante su operación. Este aspecto es especialmente relevante en sistemas con recursos limitados, como dispositivos móviles o sistemas embebidos.

Medición y notación

La complejidad espacial se mide en función de la cantidad de memoria requerida, expresada comúnmente en notación Big O, similar a la complejidad temporal.

Ejemplos en JavaScript

Búsqueda en un array (O(1))

function buscarEnArray(array, valorBuscado) {
    for (let i = 0; i < array.length; i++) {
        if (array[i] === valorBuscado) {
            return i; // Índice del elemento encontrado
        }
    }
    return -1; // Si no se encuentra el elemento
}

Este algoritmo utiliza una cantidad constante de memoria, ya que solo almacena variables simples.

Ordenamiento por burbuja (O(n))

function ordenarArray(array) {
    let longitud = array.length;
    let intercambio;
    do {
        intercambio = false;
        for (let i = 0; i < longitud - 1; i++) {
            if (array[i] > array[i + 1]) {
                [array[i], array[i + 1]] = [array[i + 1], array[i]];
                intercambio = true;
            }
        }
        longitud--;
    } while (intercambio);
    return array;
}

Este algoritmo requiere espacio proporcional al tamaño del arreglo que se ordena.

Cálculo recursivo de Fibonacci (O(n))

function fibonacci(n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

La recursión almacena múltiples llamadas en la pila, aumentando el uso de memoria proporcionalmente.

Comprender la complejidad espacial ayuda a diseñar algoritmos que no solo sean rápidos, sino también eficientes en el uso de recursos.

Algoritmo de Dijkstra: cálculo de caminos más cortos en grafos ponderados

El algoritmo de Dijkstra es una herramienta esencial para programadores que trabajan con grafos ponderados, permitiendo encontrar la ruta más corta entre dos nodos. Este algoritmo es ampliamente utilizado en sistemas de navegación, planificación de rutas y redes de transporte.

Características principales

Implementación en JavaScript

El siguiente código utiliza una lista de adyacencia para representar el grafo y calcula la distancia más corta entre dos nodos:

function dijkstra(graph, start, end) {
    let distances = {};
    let queue = [];

    for (let vertex in graph) {
        if (vertex === start) {
            distances[vertex] = 0;
            queue.push(vertex);
        } else {
            distances[vertex] = Infinity;
        }
    }

    while (queue.length) {
        let currentVertex = queue.shift();

        for (let neighbor in graph[currentVertex]) {
            let tentativeDist =
                graph[currentVertex][neighbor] + distances[currentVertex];
            if (tentativeDist < distances[neighbor]) {
                distances[neighbor] = tentativeDist;
                if (neighbor === end) {
                    return distances[neighbor];
                }
                queue.push(neighbor);
            }
        }
    }
}

Este algoritmo es fundamental para resolver problemas complejos de rutas y optimización en grafos ponderados.

Algoritmo de fuerza bruta: simplicidad en la resolución de problemas

El algoritmo de fuerza bruta es una técnica directa que prueba todas las posibles soluciones hasta encontrar la correcta. Aunque no siempre es la opción más eficiente, su simplicidad lo hace útil para problemas pequeños o cuando no existen soluciones más óptimas conocidas.

Funcionamiento y ejemplo

Imaginemos buscar el número más grande en un arreglo. En lugar de usar métodos complejos, el algoritmo compara cada elemento para identificar el mayor.

function encontrarNumeroMayor(numeros) {
    let numeroMayor = numeros[0];

    for (let i = 1; i < numeros.length; i++) {
        if (numeros[i] > numeroMayor) {
            numeroMayor = numeros[i];
        }
    }

    return numeroMayor;
}

const arreglo = [1, 5, 20, 3, 10];
console.log(encontrarNumeroMayor(arreglo)); // Output: 20

Este enfoque garantiza la solución correcta, aunque puede ser menos eficiente en conjuntos de datos grandes. Es fundamental evaluar cuándo aplicar esta técnica frente a algoritmos más avanzados.

Algoritmos de backtracking: exploración y optimización recursiva

Los algoritmos de backtracking son técnicas recursivas que exploran todas las posibles soluciones a un problema, retrocediendo cuando una opción no conduce a una solución válida. Esta estrategia es especialmente útil en problemas de búsqueda y optimización.

Funcionamiento y ejemplo en laberintos

Consideremos la búsqueda de una ruta desde un punto A hasta un punto B en un laberinto. El algoritmo avanza explorando caminos posibles y retrocede al encontrar callejones sin salida, probando alternativas hasta hallar la salida.

function encontrarCamino(x, y) {
    if (laberinto[x][y] == "B") return true; // Punto B alcanzado
    if (laberinto[x][y] == "#" || visitado[x][y]) return false; // Pared o ya visitado

    visitado[x][y] = true; // Marca como visitado

    if (encontrarCamino(x - 1, y)) return true; // Arriba
    if (encontrarCamino(x + 1, y)) return true; // Abajo
    if (encontrarCamino(x, y - 1)) return true; // Izquierda
    if (encontrarCamino(x, y + 1)) return true; // Derecha

    return false; // Sin camino viable
}

Este método construye un árbol de soluciones, explorando cada rama y retrocediendo cuando es necesario, hasta encontrar una solución o agotar las opciones.

Los algoritmos de backtracking son herramientas poderosas para resolver problemas complejos de búsqueda y optimización en programación.