En el articulo anterior "Algoritmos simples y estructuras de datos en JS". Discutimos algoritmos simples(búsquedas lineales y binarias; selección e inserción ordenada). Aquí, continúo con el concepto de complejidad y su aplicación a 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; esto puede ser por tiempo o espacio (espacio en disco) necesario para realizar una tarea específica (buscar, clasificar o acceder a los datos) en una estructura de datos determinada. La eficiencia del rendimiento de una tarea depende del número de operaciones requeridas para completarla.
Sacar la basura puede requerir 3 pasos (atar, sacar y tirar en el basurero). Sacar la basura puede ser simple, pero si la vas a sacar después de una larga semana, es posible que no puedas completar la tarea debido a la falta de espacio en el basurero.
Aspirar una habitación puede requerir muchos pasos repetitivos (encender la aspiradora, aspirar repetidamente los espacios de la habitación y apagarla). Mientras más grande sea la habitación, más tiempo llevará aspirar la habitación.
Entonces, existe una relación entre el número de operaciones realizadas y el número de elementos operados. Tener mucha basura (elementos) requiere sacarla muchas veces. Esto puede generar un problema de complejidad espacial (space complexity). Tener una gran cantidad metros cuadrados (elementos) requiere aspirar muchas veces. Esto puede dar lugar a un problema de complejidad en tiempo (time complexity).
Ya sea que esté sacando la basura o aspirando una habitación, podría decir que el orden de la operación (O) incrementa exactamente con el número de elementos (n). Si tengo 1 bolsa de basura, tengo que sacar la basura una vez. Si tengo 2 bolsas de basura, tengo que hacer la misma tarea dos veces, asumiendo que físicamente no puedo levantar más de una bola a la vez. Entonces, the Big-O de estas tareas es O = n o O = function(n) o O(n). Esto es una complejidad lineal (linear complexity) (una línea recta entre 1 operación: 1 elemento). Entonces, 30 operaciones equivalen a 30 elementos (línea amarilla del gráfico anterior).
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, es uno después del otro. Es una constante O(1), asumiendo que es el primer elemento en tu lista. Por lo tanto, si el elemento que estás buscando siempre aparece primero en la lista, independientemente del tamaño de la lista, encontrarás el elemento inmediatamente. La complejidad de la búsqueda es constante con el tamaño de la lista. El peor caso de este tipo de busqueda es de complejidad lineal o O(n). En otras palabras, para n elementos, tengo que buscar n veces antes de encontrar mi elemento, por eso es una búsqueda lineal.
Búsqueda binaria
Para búsqueda binaria, el mejor caso es O(1), esto significa que el elemento que buscas se encuentra en el centro. El peor caso es log base 2 of n o:
Logaritmo o log es la manera de expresar un exponente a una base dada. Entonces, si hay 16 elementos (n = 16), esto tomará, en el peor caso, 4 pasos para encontrar el número 15 (exponente = 4).
o simplemente: O(log n)
Ordenamiento
Ordenamiento Burbuja (Bubble)
En el ordenamiento burbuja, cada elemento es comparado con el resto de la colección para determinar el máximo valor. Por esta razón, el peor caso es de complejidad O(n²). Pensemos en un bucle dentro de otro bucle.
Entonces, por cada elemento necesitas compararlo con el resto de la colección, un total de 16 comparaciones para 4 elementos (4² = 16). En el mejor de los casos la colección ya esta ordenada, excepto por un solo elemento. Esto equivale a una sola ronda de comparaciones. Es decir, se requiren cuatro comparaciones, que es una complejidad de O(n).
Selección
A diferencia del ordenamiento burbuja, en lugar de intercambiar el valor más alto, intercambia el valor más bajo. El ordenamiento por selección selecciona el valor más bajo para intercambiarlo con las primeras posiciones. Pero, como requiere comparar cada elemento con el resto de la colección también tiene una complejidad O(n²).
Inserción
A diferencia de los ordenamientos burbuja y selección, el ordenamiento por inserción inserta los elementos en su posición correcta. Pero, igual que el ordenamiento anterior requiere comparar cada elemento con el resto de la colección, por lo tanto, tiene una complejidad de orden O(n²). Al igual que el ordenamiento burbuja, si solo queda un elemento por ordenar, solo se requiere una ronda de comparaciones para insertar el elemento en su posición correcta. Es decir, en su mejor caso tiene una complejidad O(n).
Estructuras de datos
Arreglos
Debido a que se necesita un solo paso para acceder a los elementos de un arreglo usando su índice, o agregar/eliminar un elemento al final del arreglo, la complejidad para acceder, añadir o eliminar un valor de un arreglo es O(1). Considerando, buscar linealmente a través de un arreglo usando su índice, como lo vimos antes, tiene una complejidad de O(n).
Además, debido a que un cambio de un valor hacia o desde el inicio de una matriz (shift o unshift) requiere volver a generar los índices(es decir, eliminar un elemento en el índice 0 requiere volver a etiquetar el elemento del índice 1 como índice 0, y así sucesivamente). Tiene una complejidad O(n) ya que la generación de los índices se realiza desde el inicio hasta el final del arreglo.
clave — Valor
Acceder, insertar o remover un valor usando la clave es instantáneo, por lo que se entiende complejidad O(1). Buscando en un "depósito" un elemento específico usando todas las claves disponibles es en esencia una busqueda lineal, y tiene una complejidad O(n).
Conclusión
Complejidad es más que un tema para discutir en algoritmos y estructuras de datos. Si se usa con prudencia, puede ser útil para medir la eficiencia del trabajo que se realiza y el código que se crea para resolver problemas.
Referencia
https://www.udemy.com/js-algorithms-and-data-structures-masterclass/
Traducido del artículo de Yung L. Leung - The complexity of simple algorithms and data structures in JS