Algoritmos en Javascript con ejemplos visuales

Hola programadores,

La mayoría de nosotros le tenemos miedo a los algoritmos y nunca empezamos a aprenderlos. Pero no deberíamos tenerle miedo. Un algoritmo son solo pasos para resolver un problema.

Hoy cubriremos los algoritmos principales de una manera fácil e ilustrativa.

No intente memorizarlos, el algoritmo tiene más que ver con la resolución de problemas. Entonces, siéntese con un papel y un bolígrafo.

Los términos en la tabla de contenido pueden parecer muy atemorizantes, pero quédate conmigo, prometo explicarte todo de la manera más simple posible.

Tabla de contenido:

  1. Notación Big O
  2. Entendiendo la notación Big O
  3. Algoritmos
  4. ¿Qué es un algoritmo y por qué preocuparse?
  5. Recursividad
  6. Algoritmo de búsqueda lineal
  7. Algoritmo de búsqueda binaria
  8. Algoritmo de búsqueda ingenua
  9. Algoritmo KMP
  10. Ordenamiento de burbuja
  11. Combinar Ordenar
  12. Ordenación rápida
  13. Orden de Radix

Entendiendo la notación Big O

Big O Notation es una forma de representar la complejidad temporal y espacial de un algoritmo.

  • Complejidad de tiempo: tiempo que tarda el algoritmo en completar la ejecución.
  • Complejidad espacial: la memoria que ocupa el algoritmo.
cubierta de notación-o-grande

Hay pocas expresiones (notaciones) que representen la complejidad temporal de un algoritmo.

  • O (1): Complejidad de tiempo constante. Este es el caso ideal.
  • O (log n): complejidad de tiempo logarítmico. Si log(n) = xentonces es lo mismo que10^x
  • O (n): Complejidad de tiempo lineal. El tiempo aumenta con el número de entradas de forma lineal. Por ejemplo, si una entrada tarda 1 ms, 4 entradas tardarán 4 ms en ejecutar el algoritmo.
  • O (n ^ 2): complejidad de tiempo exponencial. Esto ocurre principalmente en el caso de bucles anidados.
  • O (n!): Complejidad del tiempo factorial. Este es el peor de los casos senario, que debe evitarse.

Debe intentar escribir su algoritmo de manera que pueda ser representado por las primeras 3 notaciones. Y los dos últimos deben evitarse con la mayor frecuencia posible.

grafo-notación-o

Desea mantener su complejidad lo más baja y directa posible, idealmente evitando cualquier cosa por encima de O (n).

En otras secciones de este artículo, verá ejemplos de cada notación. Por ahora, esto es todo lo que necesita saber.

Algoritmo

¿Qué es el algoritmo y por qué preocuparse?

La forma de resolver un problema o podemos decir los pasos , el procedimiento o el conjunto de reglas para resolver un problema se conoce como Algoritmo.Ej: algoritmo del motor de búsqueda para encontrar datos relacionados con una cadena de búsqueda.

Como programador, se encontrará con muchos problemas que deben resolverse con estos algoritmos. Entonces, es mejor si ya los conoce.

Recursividad

Una función que se llama a sí misma es recursividad. Piense en ello como una alternativa al bucle.

function recursiveFn() {
    console.log("This is a recursive function");
    recursiveFn();
}

recursiveFn();

En el fragmento de código anterior, la línea 3 recursiveFn se llama en recursiveFn. Como mencioné anteriormente, la recursividad es una alternativa al bucle.

Entonces, ¿cuántas veces se ejecutará exactamente esta función?

Bueno, esto creará un bucle infinito, porque no hay nada que lo detenga en ningún momento.

diagrama de recursividad

Digamos que necesitamos ejecutar el ciclo solo 10 veces. En la undécima iteración, la función debería regresar. Eso detendrá el bucle.

let count = 1;
function recursiveFn() {
    console.log(`Recursive ${count}`);
    if (count === 10) return;
    count++;
    recursiveFn();
}

recursiveFn();

En el fragmento de código anterior, la línea 4 regresa y detiene el bucle en el conteo 10.

Ahora veamos un ejemplo más realista. Nuestra tarea es devolver una matriz de números impares de una matriz dada. Esto se puede lograr de varias formas, incluido el bucle for, el método Array.filter, etc.

Pero para mostrar el uso de la recursividad, usaré una función helperRecursive.

function oddArray(arr) {
    let result = [];
    function helperRecursiveFn(arr) {
        if(arr.length === 0) {
            return; // 1
        } else if(arr[0] % 2 !== 0) {
            result.push(arr[0]); // 2
        }
        helperRecursiveFn(arr.slice(1)); // 3
    }
    helperRecursiveFn(arr);
    return result;
}

oddArray([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
// OutPut -> [1, 3, 5, 7, 9]

Aquí la función recursiva es helperRecursiveFn.

  1. Devuelve si la longitud de la matriz es 0.
  2. Empuje el elemento a la matriz de resultados si el elemento es impar.
  3. Llame a helperRecursiveFn con el primer elemento de la matriz en rodajas . Cada vez que se cortará el primer elemento de la matriz, porque ya lo hemos verificado para par o impar.

Por ejemplo: se llamará a helperRecursiveFn por primera vez con [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. La próxima vez se llamará con [2, 3, 4, 5, 6, 7, 8, 9, 10]y así sucesivamente hasta que la longitud de la matriz sea 0.

Algoritmo de búsqueda lineal

El algoritmo de búsqueda lineal es bastante simple. Diga que necesita averiguar si existe un número en una matriz dada o no.

Ejecutará un bucle for simple y comprobará cada elemento hasta que encuentre el que está buscando.

const array = [3, 8, 12, 6, 10, 2];

// Find 10 in the given array.
function checkForN(arr, n) {
    for(let i = 0; i < array.length; i++) {
        if (n === array[i]) {
            return `${true} ${n} exists at index ${i}`;
        }
    }

  return `${false} ${n} does not exist in the given array.`;
}

checkForN(array, 10);

Ese es el algoritmo de búsqueda lineal. Busca cada elemento en la matriz uno por uno de manera lineal.

algoritmo de búsqueda lineal

Complejidad temporal del algoritmo de búsqueda lineal

Solo hay un bucle for que se ejecutará n veces. Donde n (en el peor de los casos) es la longitud de la matriz dada. Aquí, el número de iteraciones (en el peor de los casos) es directamente propicio a la entrada (matriz de longitud).

Por lo tanto, la complejidad de tiempo para el algoritmo de búsqueda lineal es Complejidad de tiempo lineal: O (n) .

Algoritmo de búsqueda binaria

En la búsqueda lineal, puede eliminar un elemento a la vez. Pero con el algoritmo de búsqueda binaria puede eliminar varios elementos a la vez. Es por eso que la búsqueda binaria es más rápida que la búsqueda lineal.

El punto que debe tenerse en cuenta aquí es que la búsqueda binaria solo funciona en una matriz ordenada .

Este algoritmo sigue el enfoque de divide y vencerás. Encuentre el índice de 8 en [2, 3, 6, 8, 10, 12].

Paso 1:
Encuentra el índice medio de la matriz.

const array = [2, 3, 6, 8, 10, 12];
let firstIndex = 0;
let lastIndex = array.length - 1;
let middleIndex = Math.floor((firstIndex + lastIndex) / 2); // middleIndex -> 2

Paso 2:
Verifique si el elemento middleIndex> 8. Si es así, eso significa que 8 está a la izquierda de middleIndex. Por lo tanto, cambie lastIndex a (middleIndex – 1).

Paso 3: De lo
contrario, si el elemento middleIndex <8. Eso significa que 8 está a la derecha de middleIndex. Por lo tanto, cambie firstIndex a (middleIndex + 1);

if (array[middleIndex] > 8) {
    lastIndex = middleIndex - 1;
} else {
    firstIndex = middleIndex + 1;
}

Paso 4:
Con cada iteración, middleIndex se establece nuevamente según el nuevo firstIndex o lastIndex.

Veamos todos esos pasos juntos en formato de código.

function binarySearch(array, element) {
    let firstIndex = 0;
    let lastIndex = array.length - 1;
    let middleIndex = Math.floor((firstIndex + lastIndex) / 2);

    while (array[middleIndex] !== element && firstIndex <= lastIndex) {
        if(array[middleIndex] > element) {
                lastIndex = middleIndex - 1;
        }else {
                firstIndex = middleIndex + 1;
        }
        middleIndex = Math.floor((firstIndex + lastIndex) / 2);
    }
    return array[middleIndex] === element ? middleIndex : -1;
}

const array = [2, 3, 6, 8, 10, 12];
binarySearch(array, 8); // OutPut -> 3

Aquí hay una representación visual del código anterior.

Paso 1

firstIndex = middleIndex + 1;

Paso 2

lastIndex = middleIndex - 1;

Paso 3

array[middleIndex] === 8 // Found It

Complejidad temporal de la búsqueda binaria

Solo hay un bucle while que se ejecutará n veces. Pero aquí el número de iteraciones no depende de la entrada (longitud de la matriz).

Por lo tanto, la complejidad de tiempo para el algoritmo de búsqueda binaria es Complejidad de tiempo logarítmica: O (log n) . Y puede consultar el gráfico de notación O. O (log n) es más rápido que O (n).

Algoritmo de búsqueda ingenua

El algoritmo de búsqueda ingenuo se utiliza para encontrar si una cadena contiene una subcadena determinada. Por ejemplo, compruebe si «helloworld» contiene la subcadena «owo».

  1. Primer bucle en la cadena principal («helloworld»).
  2. Ejecute un bucle anidado en la subcadena («owo»).
  3. Si el carácter no coincide, rompa el bucle interno; de lo contrario, siga repitiendo.
  4. Si el bucle interno se completa y tiene una coincidencia, devuelve verdadero; de lo contrario, mantén el bucle externo en funcionamiento.

Aquí hay una representación visual.

ingenuo-búsqueda-algo

Aquí está la implementación en código.

function naiveSearch(mainStr, subStr) {
    if (subStr.length > mainStr.length) return false;

    for(let i = 0; i < mainStr.length; i++) {
       for(let j = 0; j < subStr.length; j++) {
            if(mainStr[i + j] !== subStr[j]) break;
            if(j === subStr.length - 1) return true; 
        }
    }
    return false;
}

Ahora, intentemos comprender el código anterior.

  • En la línea 2, devuelve falso si la longitud de subString es mayor que la longitud de mainString.
  • En la línea 4, comience a hacer un bucle en mainString.
  • En la línea 5, inicie el bucle anidado en subString.
  • En la línea 6, rompa el bucle interno si no se encuentra ninguna coincidencia, y continúe con la siguiente iteración para el bucle externo.
  • En la línea 7, devuelve verdadero en la última iteración del bucle interno.

Complejidad temporal de la búsqueda ingenua

Hay un bucle dentro de un bucle (bucle anidado). Ambos bucles se ejecutan n veces. Por lo tanto, la complejidad del tiempo para un algoritmo de búsqueda ingenuo es (n * n) Complejidad de tiempo exponencial: O (n ^ 2) .

Y como se discutió en la parte superior, cualquier complejidad de tiempo por encima de O (n) debe evitarse si es posible. Veremos un mejor enfoque con menos complejidad de tiempo en el próximo algoritmo.

Algoritmo KMP

El algoritmo KMP es un algoritmo de reconocimiento de patrones y es un poco difícil de entender. Bien, intentemos encontrar si la cadena «abcabcabspl» contiene la subcadena «abcabs».

Si intentamos resolver esto con Naive Search Algo , coincidirá con los primeros 5 caracteres, pero no con el sexto carácter. Y tendremos que empezar de nuevo con la próxima iteración, perderemos todo el progreso en la iteración anterior.

kmp-algo-1

Entonces, para guardar nuestro progreso y usarlo, debemos usar algo llamado tabla LPS. Ahora en nuestra cadena coincidente «abcab» encontraremos el mismo prefijo y sufijo más largo.

Aquí, en nuestra cadena «abcab» «ab» es el mismo prefijo y sufijo más largo.

kmp-algo-2

Ahora, comenzaremos la siguiente iteración de búsqueda desde el índice 5 (para la cadena principal). Guardamos dos personajes de nuestra iteración anterior.

kmp-algo-4

Para averiguar el prefijo, el sufijo y desde dónde comenzar la próxima iteración, usamos la tabla LPS.

LPS para nuestra subcadena («abcabs») es «0 0 0 1 2 0».

tabla-lps

A continuación se explica cómo calcular la tabla LPS.

function calculateLpsTable(subStr) {
    let i = 1;
    let j = 0;
    let lps = new Array(subStr.length).fill(0);

    while(i < subStr.length) {
        if(subStr[i] === subStr[j]) {
            lps[i] = j + 1;
            i += 1;
            j += 1;
        } else {
            if(j !== 0) {
                j = lps[j - 1];
            } else {
                i += 1;
            }
        }
    }
    return lps;
}

Aquí está la implementación en código usando la tabla LPS.

function searchSubString(string, subString) {
    let strLength = string.length;
    let subStrLength = subString.length;
    const lps = calculateLpsTable(subString);

    let i = 0;
    let j = 0;

    while(i < strLength) {
        if (string[i] === subString[j]) {
            i += 1;
            j += 1;
        } else {
            if (j !== 0) {
                j = lps[j - 1];
            } else {
                i += 1;
            }
        }
        if (j === subStrLength) return true;
    }

    return false;
}

Complejidad temporal del algoritmo KMP

Solo hay un ciclo que se ejecuta n veces. Por lo tanto, la complejidad de tiempo para el algoritmo KMP es Complejidad de tiempo lineal: O (n) .

Observe cómo se mejora la complejidad del tiempo en comparación con la del algoritmo de búsqueda ingenuo.

Algoritmo de clasificación de burbujas

Ordenar significa reorganizar los datos en orden ascendente o descendente. La clasificación de burbujas es uno de los muchos algoritmos de clasificación.

En el algoritmo de clasificación de burbujas, intercambiamos el número más grande al final comparando cada número con el número anterior. Aquí hay una representación visual.

ordenamiento de burbuja

Implementación del código de clasificación de burbujas.

function bubbleSort(array) {
    let isSwapped;

    for(let i = array.length; i > 0; i--) {
        isSwapped = false;

        for(let j = 0; j < i - 1; j++) {
            if(array[j] > array[j + 1]) {
                [array[j], array[j+1]] = [array[j+1], array[j]];
                isSwapped = true;
            }
        }

        if(!isSwapped) {
            break;
        }
    }
    return array;
}

Intentemos comprender el código anterior.

  • Bucle desde el final de la matriz con la variable i hacia el principio.
  • Inicie el ciclo interno con la variable j hasta (i – 1).
  • Si matriz [j]> matriz [j + 1], cámbielos.
  • devolver matriz ordenada.

Complejidad temporal del algoritmo de clasificación de burbujas

Hay un ciclo anidado y ambos ciclos se ejecutan n veces, por lo que la complejidad de tiempo para este algoritmo es (n * n) que es Complejidad de tiempo exponencial O (n ^ 2) .

Combinar algoritmo de ordenación

El algoritmo de clasificación de fusión sigue el enfoque de dividir y conquistar. Es una combinación de dos cosas: fusionar y ordenar.

En este algoritmo, primero dividimos la matriz principal en múltiples matrices ordenadas individualmente.

fusionar-ordenar

Luego fusionamos los elementos ordenados individualmente en la matriz final.

Veamos la implementación en código.

Fusionar matriz ordenada

function mergeSortedArray(array1, array2) {
    let result = [];
    let i = 0;
    let j = 0;

    while(i < array1.length && j < array2.length) {
        if(array1[i] < array2[j]) {
            result.push(array1[i]);
            i++;
        } else {
            result.push(array2[j]);
            j++;
        }
    }

    while (i < array1.length) {
        result.push(array1[i]);
        i++;
    }

    while (j < array2.length) {
        result.push(array2[j]);
        j++;
    }

    return result;
}

El código anterior fusiona dos matrices ordenadas en una nueva matriz ordenada.

Combinar algoritmo de ordenación

function mergeSortedAlgo(array) {
    if(array.length <= 1) return array;

    let midPoint = Math.floor(array.length / 2);
    let leftArray = mergeSortedAlgo(array.slice(0, midPoint));
    let rightArray = mergeSortedAlgo(array.slice(midPoint));

    return mergeSortedArray(leftArray, rightArray);
}

El algoritmo anterior utiliza la recursividad para dividir la matriz en varias matrices de un solo elemento.

Complejidad de tiempo del algoritmo de clasificación por fusión

Intentemos calcular la complejidad del tiempo del algoritmo de ordenación por fusión. Entonces, tomando nuestro ejemplo anterior ([6, 3, 5, 2]), se necesitaron 2 pasos para dividirlo en una matriz de elementos únicos múltiples.

It took 2 steps to divide an array of length 4 - (2^2)

**.

Ahora, si duplicamos la longitud de la matriz (8), se necesitarán 3 pasos para dividir – (2 ^ 3). Significa que duplicar la longitud de la matriz no duplica los pasos.

Por lo tanto, la complejidad de tiempo del algoritmo de clasificación de fusión es Complejidad de tiempo logarítmica O (log n) .

Algoritmo de clasificación rápida

La clasificación rápida es uno de los algoritmos de clasificación más rápidos. En clasificación rápida, seleccionamos un solo elemento conocido como pivote y moveremos todos los elementos (más pequeños que pivote) a la izquierda de pivote.

Una representación visual.

ordenación rápida

Repetiremos este proceso para la matriz a la izquierda y derecha del pivote hasta que la matriz esté ordenada.

Implementación de código

Utilidad de pivote

function pivotUtility(array, start=0, end=array.length - 1) {
    let pivotIndex = start;
    let pivot = array[start];

    for(let i = start + 1; i < array.length; i++) {
        if(pivot > array[i]) {
            pivotIndex++;
            [array[pivotIndex], array[i]] = [array[i], array[pivotIndex]];
        }   
    }

    [array[pivotIndex], array[start]] = [array[start], array[pivotIndex]];
    return pivotIndex;
}

El código anterior identifica la posición correcta del pivote y devuelve ese índice de posición.

function quickSort(array, left=0, right=array.length-1) {
    if (left < right) {
        let pivotIndex = pivotUtility(array, left, right);
        quickSort(array, left, pivotIndex - 1);
        quickSort(array, pivotIndex + 1, right);
    }

    return array;
}

El código anterior utiliza la recursividad para seguir moviendo el pivote a su posición correcta para la matriz de pivote izquierda y derecha.

Complejidad temporal del algoritmo de clasificación rápida

MEJOR CASO: Complejidad de tiempo logarítmica – O (n log n)

CASO PROMEDIO: Complejidad de tiempo logarítmica – O (n log n)

PEOR CASO: O (n ^ 2)

Algoritmo de clasificación por radix

ordenación de radix

La ordenación por radix también se conoce como algoritmo de ordenación de cubos.

Aquí primero construimos 10 cubos de índice de 0 a 9. Luego tomamos el último carácter de cada número y empujamos el número al cubo correspondiente. Recupere el nuevo orden y repita para el penúltimo carácter de cada número.

Siga repitiendo el proceso anterior hasta que se ordene la matriz.

Implementación en código.

// Contar dígitos: el código siguiente cuenta el número de dígitos que tiene el elemento dado.

function countDigits(number) {
    if(number === 0) return 1;

    return Math.floor(Math.log10(Math.abs(number))) + 1;
}

// Obtener dígito: el código a continuación da el dígito en el índice i desde la derecha.

function getDigit(number, index) {
    const stringNumber = Math.abs(number).toString();
    const currentIndex = stringNumber.length - 1 - index;

    return stringNumber[currentIndex] ? parseInt(stringNumber[currentIndex]) : 0;
}

// MaxDigit: el siguiente fragmento encuentra el número con el máximo de dígitos.

function maxDigit(array) {
    let maxNumber = 0;

    for(let i = 0; i < array.length; i++) {
        maxNumber = Math.max(maxNumber, countDigits(array[i]));
    }

    return maxNumber;
}

// The Radix Algo: utiliza todos los fragmentos anteriores para ordenar la matriz.

function radixSort(array) {
    let maxDigitCount = maxDigits(array);

    for(let i = 0; i < maxDigitCount; i++) {
        let digitBucket = Array.from({length: 10}, () => []);

        for(let j = 0; j < array.length; j++) {
            let lastDigit = getDigit(array[j], i);
            digitBucket[lastDigit].push(array[j]);
        }

        array = [].concat(...digitBucket);
    }

    return array;
}

Complejidad temporal del algoritmo de ordenación Radix

Hay un ciclo for anidado, y sabemos que la complejidad de tiempo para un ciclo for anidado es O (n ^ 2). Pero en este caso ambos bucles for no se ejecutan n veces.

El bucle externo se ejecuta k (maxDigitCount) veces y el bucle interno se ejecuta m (longitud de la matriz) veces. Por lo tanto, la complejidad de tiempo de Radix Sort es O (kxm) – (donde kxm = n) Complejidad de tiempo lineal O (n)


Muy bien, con eso estamos al final de este post. Está bien si algunos algoritmos no le hicieron clic instantáneamente, revíselos varias veces.

Fuente

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

uno × 1 =