La complejidad de los algoritmos simples y las estructuras de datos en JS

En el artículo anterior "Un paso hacia la computación como ciencia: algoritmos simples y estructuras de datos en JS", discutimos algoritmos simples (búsquedas lineales y binarias; burbujas, ordenaciones de selección e inserción) y estructuras de datos (objetos emparejados de matriz y valor-clave ). Aquí, continúo con el concepto de complejidad y su aplicación a estos algoritmos y estructuras de datos.

Complejidad

La complejidad es un factor involucrado en un proceso complejo. Con respecto a los algoritmos y las estructuras de datos, este puede ser el tiempo o el espacio (es decir, la memoria informática) necesario para realizar una tarea específica (buscar, clasificar o acceder a datos) en una estructura de datos determinada. La eficiencia de realizar una tarea depende del número de operaciones necesarias para completar una tarea.

Sacar la basura puede requerir 3 pasos (atar una bolsa de basura, sacarla afuera y tirarla en un contenedor de basura). Sacar la basura puede ser sencillo, pero si la va a sacar después de una larga semana de renovación, es posible que no pueda completar la tarea debido a la falta de espacio en el contenedor de basura.

Aspirar una habitación puede requerir muchos pasos repetitivos (encenderlo, barrer repetidamente el cabezal de la aspiradora por el piso y apagarlo). Cuanto más grande sea una habitación, más veces tendrá que barrer el piso con un cabezal de aspiración. Por lo tanto, más tiempo llevará aspirar la habitación.

Por tanto, existe una relación causal directa entre el número de operaciones realizadas y el número de elementos sobre los que se realizan. Tener mucha basura (elementos) requiere sacarla muchas veces. Esto puede generar un problema de complejidad espacial . Tener una gran cantidad de pies cuadrados (elementos) requiere barrer un cabezal de aspiración por el piso varias veces. Esto puede dar lugar a un problema de complejidad temporal .

Ya sea que esté sacando la basura o aspirando una habitación , podría decir que el recuento de operaciones ( O ) aumenta exactamente con la cantidad de elementos ( n ) . Si tengo 1 bolsa de basura, tengo que sacar la basura una vez. Si tuviera 2 bolsas de basura, tengo que realizar la misma tarea dos veces, asumiendo que físicamente no puede levantar más de una bolsa a la vez. Entonces, el Big-O de estas tareas es O = no O = función (n) u O (n) . Esta es una complejidad lineal (una línea recta con una correspondencia de 1 operación: 1 elemento). Entonces, se realizan 30 operaciones en 30 elementos (línea amarilla en el gráfico).

Esto es similar a lo que sucede cuando se consideran algoritmos y estructuras de datos.

Búsquedas

Búsqueda lineal

El mejor caso para buscar un elemento en una lista ordenada, uno tras otro, es una constante O (1) , asumiendo que es el primer elemento de su lista. Por lo tanto, si el artículo que está buscando siempre aparece en primer lugar, independientemente del tamaño de su lista, encontrará su artículo en un instante. La complejidad de su búsqueda es constante con el tamaño de la lista. El promedio del peor caso de este tipo de búsqueda es una complejidad lineal u O (n). En otras palabras,para n elementos, tengo que buscar n veces, antes de encontrar mi elemento, por lo tanto, búsqueda lineal.

Búsqueda binaria

Para una búsqueda binaria, el mejor caso es O (1), lo que significa que el elemento de su búsqueda se encuentra en el punto medio. El peor y promedio de los casos es logaritmo base 2 de no:

El logaritmo o logaritmo es una forma de expresar un exponente para una base determinada. Entonces, si hubiera 16 elementos (n = 16), entonces se necesitarían, en el peor de los casos, 4 pasos para encontrar el número 15 (exponente = 4).

O simplemente: O (log n)

Ordena

Burbuja

En la clasificación de burbujas, cada elemento se compara con el resto de la colección para determinar el valor más alto para aumentar. Por esta razón, en promedio al peor de los casos , su complejidad es O (n²) . Piense en un bucle anidado dentro de otro bucle.

Entonces, para cada artículo, lo está comparando con el resto de su colección. Esto equivale a 16 comparaciones (u operaciones) para 4 elementos (4² = 16). El mejor caso es si su colección está casi ordenada, excepto por un solo artículo. Esto equivaldría a una sola ronda de comparaciones. Es decir, se requieren cuatro comparaciones para hacer burbujear un miembro de una colección de cuatro elementos, que es una complejidad de O (n) .

Selección

A diferencia de la clasificación de burbujas , en lugar de generar el valor más alto, la clasificación de selección selecciona el valor más bajo para intercambiarlo a las primeras posiciones. Pero, debido a que requiere comparar cada elemento con el resto de la colección, también tiene una complejidad de O (n²) .

Inserción

A diferencia de los tipos de burbuja y selección , el tipo de inserción inserta el elemento en su posición correcta. Pero, al igual que los tipos anteriores, esto también requiere comparar cada elemento con el resto de la colección, por lo tanto, tiene una complejidad promedio al peor de los casos de O (n²) . Al igual que la clasificación de burbujas , si solo queda un elemento por ordenar, solo se requiere una única ronda de comparaciones para insertar el elemento en su posición correcta. Es decir, tiene la mejor complejidad de caso de O (n) .

Estructuras de datos

Matrices

Debido a que se necesita un solo paso para acceder a un elemento de una matriz a través de su índice, o agregar / eliminar un elemento al final de una matriz, la complejidad para acceder , presionar o hacer estallar un valor en una matriz es O (1) . Mientras que, buscar linealmente a través de una matriz a través de su índice, como se vio antes, tiene una complejidad de O (n) .

Además, debido a un cambio o unshift de un valor a o desde la parte frontal de una matriz requiere reindexar cada elemento que le sigue (es decir, la eliminación de un elemento en el índice 0 requiere elemento de cambio de etiqueta en el índice 1 como índice 0, y así sucesivamente), tienen una complejidad de O (n) . El reetiquetado se lleva a cabo desde el principio hasta el final de la matriz.

Clave - Objetos emparejados de valor

Acceder , insertar o eliminar un valor mediante una clave es instantáneo, por lo que tienen una complejidad de O (1) . Buscar en cada “caja de depósito” un artículo específico utilizando todas las claves disponibles es esencialmente una búsqueda lineal . Y entonces, tiene una complejidad de O (n) .

Conclusión

La complejidad es más que un tema para discutir algoritmos y estructuras de datos establecidos. Si se usa con prudencia, puede ser una herramienta útil para medir la eficiencia del trabajo que realiza y el código que crea para resolver sus problemas.

Referencia:

//www.udemy.com/js-algorithms-and-data-structures-masterclass/