Algoritmos a la Manera Caballerosa

Notación Big O

"Cómo el código se ralentiza a medida que crece la cantidad de datos"

  1. El rendimiento de un algoritmo depende de la cantidad de datos que se le proporciona.
  2. Número de pasos necesarios para completar. Algunas máquinas ejecutan algoritmos más rápido que otras, por lo que simplemente tomamos el número de pasos necesarios.
  3. Ignorar operaciones más pequeñas, constantes. O(N + 1) -> O(N) donde N representa la cantidad de datos.
function sumar(n: number): number {
  let suma = 0;

  for(let i = 0; i < n; i++) {
    suma += i;
  }

  return suma;
}

// si n es igual a 10, entonces O(N) son 10 pasos, si n es igual a 100, entonces O(N) son 100 pasos

Aquí podemos ver que O(N) es lineal, lo que significa que la cantidad de pasos depende del número de datos que se nos proporciona.

function saludar(nombre: string):  string{
  return `¡Hola ${nombre}!`
}

// si n es igual a 10, entonces O(1) son 3 pasos... ¿3? ¡SÍ, 3 pasos!

// 1 - Crear nuevo objeto de cadena para almacenar el resultado (asignando memoria para la nueva cadena)
// 2 - Concatenar la cadena '¡Hola' con el resultado.
// 3 - Devolver la cadena concatenada.

Pero ahora tenemos O(1) ya que la cantidad de pasos no depende de la cantidad de datos que se nos proporciona, siempre será 1.

Conocimientos Previos Necesarios

  • El 'Logaritmo' de un número es la potencia a la que se debe elevar la base para producir ese número. Por ejemplo, el logaritmo base 2 de 8 es 3 porque 2^3 = 8.

  • 'Lineal' significa que el número de pasos crece linealmente con la cantidad de datos.

  • El 'Cuadrático' de un número es el cuadrado de ese número. Por ejemplo, el cuadrado de 3 es 9 porque 3^2 = 9.

  • 'Exponencial' de un número es la potencia de la base elevada a ese número. Por ejemplo, el exponencial de 2 elevado a la potencia de 3 es 8 porque 2^3 = 8.

  • 'Factorial' de un número es el producto de todos los enteros positivos menores o iguales a ese número. Por ejemplo, el factorial de 3 es 6 porque 3! = 3 * 2 * 1 = 6.

  • 'Quicksort' es un algoritmo de ordenación que utiliza la estrategia de dividir y conquistar para ordenar una matriz. Es una ordenación por comparación y no es estable. Divide y vencerás es una estrategia para resolver un problema dividiéndolo en partes más pequeñas y resolviendo cada parte individualmente.

Tipos de Notación Big O

- O(1) - Tiempo constante - Siempre el mismo número de pasos independientemente de la cantidad de datos
- O(log N) - Tiempo logarítmico - El número de pasos crece logarítmicamente (búsqueda binaria)
- O(N) - Tiempo lineal - El número de pasos crece linealmente (bucles)
- O(N log N) - Tiempo linealítmico - El número de pasos crece linealítmicamente (ordenación rápida)
- O(N^2) - Tiempo cuadrático - El número de pasos crece cuadráticamente (bucles anidados)
- O(2^N) - Tiempo exponencial - El número de pasos crece exponencialmente (algoritmos recursivos)
- O(N!) - Tiempo factorial - El número de pasos crece factorialmente (algoritmos de fuerza bruta, aquellos que prueban todas las soluciones posibles)

Ejemplo con N igual a 1000:

- O(1) - 1 paso
- O(log N) - 10 pasos
- O(N) - 1000 pasos, mil pasos
- O(N log N) - 10000 pasos, diez mil pasos
- O(N^2) - 1000000 pasos, un millón de pasos
- O(2^N) - 2^1000 pasos
- O(N!) - 1000! pasos, factorial de 1000

La idea principal es que queremos evitar los algoritmos de tiempo exponencial y factorial ya que crecen muy rápido y no son eficientes en absoluto, A MENOS que estemos seguros de que la cantidad de datos que se nos proporciona es muy pequeña, ya que en realidad puede ser más rápido que otros algoritmos.

Calificación de letras para la Notación Big O, de mejor a peor, teniendo en cuenta que estamos utilizando un gran conjunto de datos:

- O(1) - Tiempo constante - A
- O(log N) - Tiempo logarítmico - B
- O(N) - Tiempo lineal - C
- O(N log N) - Tiempo linealítmico - D
- O(N^2) - Tiempo cuadrático - F
- O(2^N) - Tiempo exponencial - F
- O(N!) - Tiempo factorial - F

Ejemplos usando código

O(1) - Tiempo constante

  function sayHi(n: string):  string{
    return `Hola ${n}`
  }

Aquí está por qué es O(1):

  • El algoritmo realiza una cantidad constante de trabajo, independientemente del tamaño de la entrada.
  • El número de pasos necesarios para completar el algoritmo no depende del tamaño de la entrada.

Por lo tanto, la complejidad temporal del algoritmo es O(1) en todos los casos.

O(log N) - Tiempo logarítmico

  // teniendo el siguiente array que representa los números del 0 al 9 en orden
  const arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

  // queremos encontrar el índice de un número en el array ordenado
  function binarySearch(arr: number[], target: number): number {
    // inicializamos los punteros izquierdo y derecho
    let left = 0;
    let right = arr.length - 1;

    // mientras que left sea menor o igual que right, seguimos buscando el target
    while (left <= right) {
      // obtenemos el medio del array para compararlo con el target
        // iteramos usando el medio del array para encontrar el target porque sabemos que el array está ordenado y podemos descartar la mitad del array en cada iteración
      const mid = Math.floor((left + right) / 2); // índice medio
      const midValue = arr[mid]; // valor medio

      // si el valor medio es el target, devolvemos el índice
      if (midValue === target) {
        return mid;
      }

      // si el valor medio es menor que el target, buscamos el lado derecho del array actualizando el puntero izquierdo
      if (midValue < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    return -1; // target no encontrado
  }

En la búsqueda binaria, el algoritmo divide continuamente el intervalo de búsqueda a la mitad hasta que se encuentra el elemento objetivo o el intervalo de búsqueda se vacía. Con cada iteración, el algoritmo descarta la mitad del espacio de búsqueda en función de una comparación con el elemento medio del intervalo actual.

Aquí está por qué es O(log N):

  • En cada iteración del bucle while, el espacio de búsqueda se divide a la mitad.
  • Este proceso de división continúa hasta que el espacio de búsqueda se reduce a un solo elemento o se encuentra el objetivo.
  • Dado que el espacio de búsqueda se divide a la mitad en cada iteración, el número de iteraciones requeridas para alcanzar el elemento objetivo crece de forma logarítmica con el tamaño del array de entrada.

Por lo tanto, la complejidad temporal de la búsqueda binaria es O(log N) en promedio.

O(N) - Tiempo lineal

  function sum(n: number): number {
    let sum = 0;
    for(let i = 0; i < n; i++) {
      sum += i;
    }
    return sum;
  }

Aquí está por qué es O(N):

  • El algoritmo itera sobre el array de entrada una vez, realizando una cantidad constante de trabajo para cada elemento.
  • El número de iteraciones es directamente proporcional al tamaño del array de entrada.
  • A medida que aumenta el tamaño de la entrada, el número de pasos necesarios para completar el algoritmo crece linealmente.

Por lo tanto, la complejidad temporal del algoritmo es O(N) en el peor de los casos.

O(N log N) - Tiempo linealítmico

  // teniendo el siguiente array
  const arr = [5, 3, 8, 4, 2, 1, 9, 7, 6];

  // queremos ordenar el array usando el algoritmo quick sort
  function quickSort(arr: number[]): number[] {
    // primero verificamos si el array tiene solo un elemento o ningún elemento
    if (arr.length <= 1) {
      return arr;
    }

    // obtenemos el pivote como el último elemento del array, el pivote es el elemento con el que vamos a comparar el resto de los elementos
    const pivot = arr[arr.length - 1];

    // creamos dos arrays, uno para los elementos menores que el pivote y otro para los elementos mayores que el pivote
    const left = [];
    const right = [];

    // iteramos sobre el array y comparamos cada elemento con el pivote
    for (let i = 0; i < arr.length - 1; i++) {
      // si el elemento es menor que el pivote, lo agregamos al array izquierdo
      if (arr[i] < pivot) {
        left.push(arr[i]);
      } else {
        // si el elemento es mayor que el pivote, lo agregamos al array derecho
        right.push(arr[i]);
      }
    }

    // llamamos recursivamente a la función quickSort en los arrays izquierdo y derecho y concatenamos los resultados
    return [...quickSort(left), pivot, ...quickSort(right)];
  }

Aquí está por qué es O(N log N):

  • El algoritmo divide el array en dos subarrays basados en un elemento pivote y ordena recursivamente estos subarrays.
  • Cada paso de particionamiento implica iterar sobre todo el array una vez, lo que lleva un tiempo O(N). Sin embargo, el array suele dividirse de tal manera que el tamaño de los subarrays se reduce con cada llamada recursiva. Esto resulta en una complejidad temporal de O(N log N) en promedio.

O(N^2) - Tiempo cuadrático

  // Dado el siguiente arreglo
  const arr = [5, 3, 8, 4, 2, 1, 9, 7, 6];

  // Queremos ordenar el arreglo usando el algoritmo de ordenamiento burbuja
  function bubbleSort(arr: number[]): number[] {

    // Iteramos sobre el arreglo
    for (let i = 0; i < arr.length; i++) {

      // Iteramos sobre el arreglo nuevamente
      for (let j = 0; j < arr.length - 1; j++) {

        // Comparamos elementos adyacentes y los intercambiamos si están en el orden incorrecto
        if (arr[j] > arr[j + 1]) {
          
          // Intercambiamos los elementos
          const temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
        }
      }
    }
    return arr;
  }

Aquí está por qué es O(N^2):

  • El ordenamiento burbuja funciona repasando la lista repetidamente, comparando elementos adyacentes y cambiándolos si están en el orden incorrecto.
  • En el peor de los casos, donde el arreglo está en orden inverso, el ordenamiento burbuja necesitará hacer N pasadas a través del arreglo, cada pasada requiriendo N-1 comparaciones e intercambios.
  • Esto resulta en un total de N * (N-1) comparaciones e intercambios, lo que se simplifica a O(N^2) en términos de complejidad temporal.

O(2^N) - Tiempo exponencial

  // Queremos calcular el enésimo número de Fibonacci usando un algoritmo recursivo
  function fibonacci(n: number): number {

    // Verificamos si n es 0 o 1 como el caso base de la recursión porque la secuencia de Fibonacci comienza con 0 y 1
    if (n <= 1) {
      return n;
    }

    // Llamamos recursivamente a la función fibonacci para calcular el enésimo número de Fibonacci
    return fibonacci(n - 1) + fibonacci(n - 2);
  }

Aquí está por qué es O(2^N):

  • En cada llamada recursiva a la función fibonacci, se realizan dos llamadas recursivas adicionales con n - 1 y n - 2 como argumentos.
  • Esto conduce a un crecimiento exponencial en el número de llamadas recursivas a medida que n aumenta.
  • Cada nivel de recursión se bifurca en dos llamadas recursivas, lo que resulta en una estructura de llamadas recursivas similar a un árbol binario.
  • El número de llamadas de función se duplica con cada nivel de recursión, lo que lleva a un total de 2^N llamadas de función al calcular el enésimo número de Fibonacci.

Por lo tanto, la complejidad temporal del algoritmo es O(2^N) en el peor de los casos.

O(N!) - Tiempo factorial

  // Dado el siguiente arreglo
  const arr = [1, 2, 3];

  // Queremos generar todas las permutaciones de un arreglo dado usando un algoritmo recursivo
  function permute(arr: number[]): number[][] {
    // Caso base: si el arreglo tiene solo un elemento, devolverlo como una sola permutación
    if (arr.length <= 1) {
      return [arr];
    }

    // Inicializamos un arreglo vacío para almacenar las permutaciones
    const result: number[][] = [];

    // Iteramos sobre cada elemento en el arreglo
    for (let i = 0; i < arr.length; i++) {
      // Generamos todas las permutaciones del arreglo excluyendo el elemento actual
      const rest = arr.slice(0, i).concat(arr.slice(i + 1));
      const permutations = permute(rest);

      // Agregamos el elemento actual al principio de cada permutación
      for (const perm of permutations) {
        result.push([arr[i], ...perm]);
      }
    }
    return result;
  }

Aquí está por qué es O(N!):

  • En cada llamada recursiva a la función permute, el algoritmo genera permutaciones seleccionando cada elemento del arreglo como el primer elemento y luego generando recursivamente permutaciones de los elementos restantes.
  • El número de permutaciones crece factorialmente con el tamaño del arreglo de entrada.
  • Para cada elemento en el arreglo, hay (N-1)! permutaciones de los elementos restantes, donde N es el número de elementos en el arreglo.
  • Por lo tanto, el número total de permutaciones es N * (N-1) * (N-2) * ... * 1, que es factorial de N (N!).

Por lo tanto, la complejidad temporal del algoritmo es O(N!) en el peor de los casos.

Complejidad en el Peor Caso, el Mejor Caso y el Caso Promedio

  • La complejidad temporal en el peor de los casos representa el número máximo de pasos que tarda un algoritmo en completarse para un tamaño de entrada dado. Proporciona un límite superior sobre el rendimiento del algoritmo. Es la medida más comúnmente utilizada de la complejidad temporal en entrevistas de trabajo.

  • La complejidad temporal en el mejor de los casos representa el número mínimo de pasos que tarda un algoritmo en completarse para un tamaño de entrada dado. Proporciona un límite inferior sobre el rendimiento del algoritmo. Es menos informativa que la complejidad en el peor de los casos y rara vez se usa en la práctica.

  • La complejidad temporal en el caso promedio representa el número esperado de pasos que tarda un algoritmo en completarse para un tamaño de entrada dado, promediado sobre todas las entradas posibles. Proporciona una estimación más realista del rendimiento de un algoritmo que la complejidad en el peor de los casos. Sin embargo, calcular la complejidad en el caso promedio puede ser desafiante y a menudo se evita a favor de la complejidad en el peor de los casos.

Complejidad espacial

La complejidad espacial de un algoritmo es una medida de la cantidad de memoria que requiere para ejecutarse en función del tamaño de la entrada. Se suele expresar en términos de la cantidad máxima de memoria utilizada por el algoritmo en cualquier momento durante su ejecución.

Es importante distinguir entre la complejidad temporal y la complejidad espacial, ya que un algoritmo con buena complejidad temporal puede tener una complejidad espacial deficiente, y viceversa. Por ejemplo, un algoritmo recursivo con complejidad temporal exponencial también puede tener complejidad espacial exponencial debido a las llamadas recursivas que consumen memoria.

Pero algo a tener en cuenta es que la complejidad espacial no es tan importante como la complejidad temporal, ya que la memoria suele ser más económica que la potencia de procesamiento y, en escenarios de la vida real, generalmente omitimos el análisis de complejidad espacial y nos enfocamos en la complejidad temporal.

Imagina que estás en un asado tradicional argentino. Tienes espacio limitado en la parrilla (similar a la memoria limitada en la informática), y quieres optimizar cuánta carne puedes cocinar a la vez.

Ahora, comparemos la carne con los datos en un algoritmo. Cuando estás cocinando, tienes que considerar cuánto espacio ocupa cada corte de carne en la parrilla. De manera similar, en la informática, los algoritmos tienen que considerar cuánto espacio en memoria necesitan para almacenar y procesar datos.

Pero aquí está la cuestión: en un asado, lo más importante suele ser cuán rápido puedes cocinar la carne y servirla a tus invitados. De manera similar, en la informática, el tiempo que tarda un algoritmo en ejecutarse (complejidad temporal) suele ser el factor más crítico para el rendimiento.

Por lo tanto, si bien es esencial tener en cuenta cuánto espacio utiliza tu algoritmo, generalmente es más interesante centrarse en qué tan eficientemente puede resolver un problema en términos de tiempo.

Por supuesto, en algunas situaciones, como si estás cocinando en un balcón pequeño o cocinando para una multitud, el espacio se vuelve más importante. De manera similar, en informática, si estás trabajando con recursos de memoria limitados o en un dispositivo con restricciones estrictas de memoria, deberás prestar más atención a la complejidad espacial.

Pero en general, al igual que en un asado argentino, el equilibrio entre la complejidad temporal y espacial es clave para crear un resultado delicioso (o eficiente)!

Sin embargo, hablemos de cómo se calcula la complejidad espacial, o "cuánto espacio ocupas" en el caso de nuestra analogía de asado. Al igual que evaluarías cuánto espacio ocupa cada corte de carne en la parrilla, en informática, necesitas considerar cuánta memoria consume cada estructura de datos o variable en tu algoritmo.

Aquí hay un enfoque básico para calcular la complejidad espacial:

  1. Identifica las Variables y Estructuras de Datos: Observa el algoritmo e identifica todas las variables y estructuras de datos que utiliza. Estas podrían ser matrices, objetos u otros tipos de variables.

  2. Determina el Espacio Utilizado por Cada Variable: Para cada variable o estructura de datos, determina cuánto espacio ocupa en memoria. Por ejemplo, una matriz de enteros ocupará espacio proporcional al número de elementos multiplicado por el tamaño de cada entero.

  3. Suma el Espacio: Una vez que hayas determinado el espacio utilizado por cada variable, súmalos todos para obtener el espacio total utilizado por el algoritmo.

  4. Considera el Espacio Auxiliar: No olvides tener en cuenta cualquier espacio adicional utilizado por estructuras de datos auxiliares o llamadas de funciones. Por ejemplo, si tu algoritmo utiliza recursión, deberás considerar el espacio utilizado por la pila de llamadas.

  5. Expresa la Complejidad Espacial: Finalmente, expresa la complejidad espacial utilizando la notación Big O, al igual que haces con la complejidad temporal. Por ejemplo, si el espacio utilizado crece linealmente con el tamaño de la entrada, lo expresarías como O(N). Si crece cuadráticamente, lo expresarías como O(N^2), y así sucesivamente.

Entonces, al igual que gestionas cuidadosamente el espacio en tu parrilla para que quepa la mayor cantidad de carne posible sin amontonarla, en informática, quieres optimizar el uso de memoria para almacenar y procesar datos de manera eficiente. Y al igual que encontrar el equilibrio perfecto entre carne y espacio en un asado argentino, encontrar el equilibrio adecuado entre la complejidad temporal y espacial en tu algoritmo es clave para crear un resultado delicioso (o eficiente)!

¡Ejemplo de tiempo!

Utilicemos un algoritmo simple para encontrar la suma de elementos en una matriz como ejemplo para calcular la complejidad espacial.

function sumArray(arr: number[]): number {
    let sum = 0;  // Espacio utilizado por la variable sum: O(1)

    for (let num of arr) {  // Espacio utilizado por la variable de bucle: O(1)
        sum += num;  // Espacio utilizado por la variable temporal: O(1)
    }

    return sum;  // Espacio utilizado por el valor devuelto: O(1)
}

En este ejemplo:

  1. Tenemos una variable sum para almacenar la suma de los elementos, que ocupa una cantidad constante de espacio, denotada como O(1).
  2. Tenemos una variable de bucle num que itera a través de cada elemento de la matriz. También ocupa una cantidad constante de espacio, O(1).
  3. Dentro del bucle, tenemos una variable temporal para almacenar la suma de cada elemento con sum, que nuevamente ocupa una cantidad constante de espacio, O(1).
  4. El valor devuelto de la función es la suma, que también ocupa una cantidad constante de espacio, O(1).

Dado que cada variable y estructura de datos en este algoritmo ocupa una cantidad constante de espacio, la complejidad espacial total de este algoritmo es O(1).

En resumen, la complejidad espacial de este algoritmo es constante, independientemente del tamaño de la matriz de entrada.

Ahora consideremos un ejemplo donde creamos una nueva matriz para almacenar la suma acumulativa de elementos de la matriz de entrada.

Aquí está el algoritmo:

function cumulativeSum(arr: number[]): number[] {
    const result = []; // Espacio utilizado por la matriz resultante: O(N), donde N es el tamaño de la matriz de entrada
    let sum = 0;  // Espacio utilizado por la variable sum: O(1)
    for (let num of arr) {  // Espacio utilizado por la variable de bucle: O(1)
        sum += num;  // Espacio utilizado por la variable temporal: O(1)
        result.push(sum);  // Espacio utilizado por el nuevo elemento en la matriz resultante: O(1), pero ejecutado N veces
    }
    return result;  // Espacio utilizado por el valor devuelto (la matriz resultante): O(N)
}

En este ejemplo:

  1. Tenemos una variable result para almacenar la suma acumulativa de elementos, que crece linealmente con el tamaño de la matriz de entrada arr. Cada elemento agregado a result contribuye a la complejidad espacial. Por lo tanto, el espacio utilizado por result es O(N), donde N es el tamaño de la matriz de entrada.
  2. Tenemos una variable de bucle num que itera a través de cada elemento de la matriz de entrada arr, que ocupa una cantidad constante de espacio, O(1).
  3. Dentro del bucle, tenemos una variable temporal sum para almacenar la suma acumulativa de elementos, que ocupa una cantidad constante de espacio, O(1).
  4. Dentro del bucle, agregamos un nuevo elemento a la matriz result para cada elemento en la matriz de entrada. Cada operación de agregado agrega un elemento a la matriz, por lo que también contribuye a la complejidad espacial. Sin embargo, como se ejecuta N veces (donde N es el tamaño de la matriz de entrada), el espacio utilizado por las operaciones de agregado es O(N).
  5. El valor devuelto de la función es la matriz result, que ocupa O(N) espacio.

En general, la complejidad espacial de este algoritmo es O(N), donde N es el tamaño de la matriz de entrada. Esto se debe a que el espacio utilizado por la matriz result crece linealmente con el tamaño de la entrada.

Arreglos

Cuando hablamos de arreglos, generalmente pensamos en colecciones ordenadas de elementos, ¿verdad? Pero en JavaScript, los arreglos son en realidad objetos. Entonces, ¿qué es un arreglo real, podrías preguntar? Bueno, un verdadero arreglo es un bloque contiguo de memoria donde cada elemento ocupa la misma cantidad de espacio.

En un arreglo real, acceder a un elemento es súper rápido: es una operación de tiempo constante, lo que significa que lleva la misma cantidad de tiempo sin importar cuán grande sea el arreglo. ¿Por qué? Porque puedes calcular exactamente dónde está cada elemento en la memoria.

Ahora, contrastemos eso con los arreglos de JavaScript. Se implementan como objetos, donde los índices son las claves. Entonces, cuando accedes a un elemento en un arreglo de JavaScript, en realidad estás accediendo a una propiedad de un objeto. Esto significa que acceder a elementos no es tan rápido; es una operación de tiempo lineal porque el motor de JavaScript tiene que buscar a través de las claves del objeto para encontrar la correcta.

Para encontrar la ubicación en memoria de un elemento en un arreglo real, usas una fórmula simple:

const index = base_address + offset * size_of_element;

Aquí, el índice es lo que usualmente llamamos el índice, pero es más como un desplazamiento. La base_address es el punto de inicio del arreglo en la memoria, y size_of_element es, bueno, el tamaño de cada elemento.

Con esta fórmula, cada vez que buscas un elemento, estás realizando una operación de tiempo constante porque no importa cuán grande sea el arreglo, las matemáticas permanecen iguales.

Ahora, ilustremos esto con algo de código:

// Creemos un nuevo arreglo con 5 elementos
const a = [1, 2, 3, 4, 5];

// Calculemos el espacio total que ocupa el arreglo en memoria
const totalSpace = array.length * 4; // asumiendo que cada elemento ocupa 4 bytes

// Elijamos un índice
const index = 3;

// Calculemos la ubicación en memoria del elemento
const sizeOfEachElement = 4; // cada elemento ocupa 4 bytes
const baseAddress = array; // la referencia al propio arreglo
const offset = index * sizeOfEachElement;
const memoryLocation = baseAddress + offset;

// Accedamos al elemento en la ubicación en memoria calculada
const elementAtIndex = memoryLocation;

console.log("El valor en el índice", index, "es:", elementAtIndex); // El valor en el índice 3 es: 4

En este ejemplo, estamos simulando cómo funciona un arreglo real bajo el capó. Calculamos la ubicación en memoria de un elemento usando el índice, y luego accedemos a esa ubicación en memoria para obtener el elemento.

Ahora, visualicemos esto con Node.js, donde podemos echar un vistazo a lo que está sucediendo en la memoria:

// Creamos un nuevo búfer de arreglo en Node.js
const buffer = new ArrayBuffer(16); // 16 bytes de memoria

// Verifiquemos el tamaño del búfer (en bytes)
console.log("buffer.byteLength: " + buffer.byteLength); // Salida: buffer.byteLength: 16

// Ahora creemos una nueva Int8Array, un arreglo tipado de enteros con signo de 8 bits
const int8Array = new Int8Array(buffer);

// Registremos el contenido de la Int8Array (todos ceros inicialmente)
console.log(int8Array); // Salida: Int8Array(16) [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

// Cada elemento en la Int8Array representa un solo byte en el búfer

// Ahora cambiemos el valor del primer elemento del arreglo a 1
int8Array[0] = 1;

// Registremos nuevamente el contenido de la Int8Array y del búfer
console.log(int8Array); // Salida: Int8Array(16) [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
console.log(buffer); // Observa cómo el búfer subyacente también se modifica (el primer byte se convierte en 1)
// Salida: Búfer después del cambio: ArrayBuffer { [Uint8Contents]: <01 

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00> }

// Las TypedArrays proporcionan una vista diferente de la misma memoria

// Ahora creemos un arreglo de enteros con signo de 16 bits (usa 2 bytes por elemento)
const int16Array = new Int16Array(buffer);

// Registremos el contenido de la Int16Array (valores iniciales basados en el búfer)
console.log(int16Array); // Salida: Int16Array(8) [1, 0, 0, 0, 0, 0, 0, 0]

// La Int16Array tiene menos elementos porque usa más bytes por elemento, 2 bytes

// Nuevamente, cambiemos un valor (tercer elemento) y observemos los efectos
int16Array[2] = 4000;

// Registremos el contenido de los tres arreglos y el búfer
console.log(int16Array); // Salida: Int16Array(8) [1, 0, 4000, 0, 0, 0, 0, 0]
console.log(buffer); // Observa cómo se modifican múltiples bytes en el búfer (quinto y sexto bytes)
// Salida: ArrayBuffer { [Uint8Contents]: <01 00 00 00 a0 0f 00 00 00 00 00 00 00 00 00 00> } (los contenidos se modifican, por ejemplo, el quinto byte podría ser 0x0f)
console.log(int8Array); // La vista de la Int8Array también se ve afectada (los quinto y sexto bytes cambian)
// Salida: Int8Array(16) [1, 0, 0, 0, -96, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] (el quinto byte es -96, el sexto byte es 15, se muestra en decimal)

// Ahora creemos un arreglo de enteros con signo de 32 bits (usa 4 bytes por elemento)
const int32Array = new Int32Array(buffer);

// Registremos el contenido de la Int32Array (valores iniciales basados en el búfer)
console.log(int32Array); // Salida: Int32Array(4) [1, 4000, 0, 0]

// Incluso menos elementos debido al mayor tamaño de cada elemento, 4 bytes

// Cambiemos el valor y observemos los efectos
int32Array[2] = 100000;

// Registremos el contenido de los tres arreglos y el búfer
console.log(int32Array); // Salida: Int32Array(4) [1, 4000, 100000, 0]
console.log(buffer); // ArrayBuffer { [Uint8Contents]: <01 00 00 00 a0 0f 00 00 10 27 00 00 00 00 00 00> } aún más bytes en el búfer se modifican (noveno, décimo, undécimo, duodécimo)
console.log(int16Array); // Int16Array(8) [1, 0, 4000, 0, 10000, 0, 0, 0] (el cuarto elemento ahora es 10000)
console.log(int8Array); // Int8Array(16) [1, 0, 0, 0, -96, 15, 0, 0, 16, 39, 0, 0, 0, 0, 0, 0] (los noveno, décimo, undécimo, duodécimo bytes ahora son 16, 39)

En este ejemplo de Node.js, estamos creando un búfer de 16 bytes, que es como un bloque de memoria. Luego, creamos diferentes arreglos tipados para ver esta memoria de manera diferente, como arreglos de diferentes tipos de enteros. Modificar uno de estos arreglos también cambia el búfer subyacente, mostrando cómo son vistas diferentes de la misma memoria.

Ahora, volvamos al por qué estamos viendo decimales. Necesitaremos entender primero la representación de complemento a dos.

Entonces, el complemento a dos es como el truco mágico que usamos en la informática para manejar tanto números positivos como negativos usando el mismo sistema binario. Imagina esto: en nuestros números binarios, el primer dígito desde la izquierda (el jefe grande, ¿sabes?) decide si el número es positivo o negativo. Si es 0, es positivo, y si es 1, es negativo.

Ahora, para los números positivos, es pan comido. Solo los escribes en binario, como de costumbre. Por ejemplo, el número 3 en binario de 8 bits es 00000011. No hay problema allí, ¿verdad?

Pero cuando se trata de números negativos, necesitamos un truco. Tomamos la representación binaria del número positivo, invertimos todos los bits (los 0 se convierten en 1 y los 1 se convierten en 0), y luego sumamos 1 al resultado. Esto nos da el complemento a dos del número negativo. Digamos que queremos representar -3. Primero, empezamos con la representación binaria de 3, que es 00000011. Luego, invertimos todos los bits para obtener 11111100, y finalmente, sumamos 1 a este resultado para obtener 11111101. Ese es el complemento a dos de -3 en binario de 8 bits.

Ahora, ¿por qué hacemos todo esto? Bueno, es porque en informática nos gusta que las cosas estén ordenadas y sean consistentes. Con el complemento a dos, podemos usar las mismas reglas para sumar y restar tanto números positivos como negativos, sin necesidad de preocuparnos por casos especiales. Mantiene nuestra matemática bonita y limpia, como tomar mate en un día soleado en Buenos Aires.

Ahora podemos ver por qué estamos viendo decimales.

Cuando trabajas con 8 bits, los valores se representan en decimal, ya que el rango de un entero de 8 bits con signo es de -128 a 127. Si el valor se desborda, se envuelve dentro del rango:

Cuando lidias con 8 bits, los valores se muestran en decimal porque, ya sabes, un entero de 8 bits con signo solo puede contener números de -128 a 127. Es como tener un espacio limitado en un autobús lleno: solo puedes meter a tanta gente.

Ahora, imagina que estás tratando de meter el número 4000. En binario, eso es 111110100000. Pero aquí está la cosa: nuestro autobús solo llega hasta 127. Entonces, cuando intentas meter 4000 allí, es como intentar meter a un equipo de fútbol en un auto pequeño, simplemente no va a suceder.

Cuando intentas meter 4000 en nuestro autobús de 8 bits, se desborda. Pero en lugar de causar caos, hace algo bastante genial: se envuelve. Ves, la ruta del autobús comienza de nuevo desde el principio, como un bucle interminable.

Este "envolver" es donde las cosas se ponen interesantes. El bit más a la izquierda, el gran jefe del número, cambia su signo. Entonces, en lugar de ser positivo, se vuelve negativo. Es como dar la vuelta al autobús yendo en la dirección opuesta.

Ahora, usamos nuestro truco anterior llamado complemento a dos para averiguar el nuevo número. Primero, invertimos todos los bits de 111110100000 para obtener 000001011111. Luego, sumamos 1 a este número invertido, dándonos 000001100000.

¡Y voilà! Ese número binario 000001100000 representa -96 en decimal. Entonces, aunque intentaste meter 4000, nuestro pequeño autobús lo maneja como un campeón y te dice que es -96. ¡Esa es la magia del desbordamiento y el envolvimiento en un mundo de 8 bits!

¿Cómo pensar?

Cuando estás hasta el cuello de código, entender los conceptos y aplicarlos para resolver esos problemas es la clave. ¿Mi consejo? Echa el resto comentando tu código, explicando cada paso dentro del método y DESPUÉS lánzate de lleno a la implementación.

Así sabrás qué hacer y solo necesitarás descubrir cómo hacerlo.

Ejemplo:

function sumArray(arr: number[]): number {
		// Inicializa la variable de suma para almacenar la suma de elementos
		let sum = 0;  // O(1)

		// Itera sobre cada elemento en el array
		for (let num of arr) {  // O(N)
				// Suma el elemento actual a la suma
				sum += num;  // O(1)
		}

		// Devuelve la suma final
		return sum;  // O(1)
}

Búsqueda Lineal

Es el pan de cada día de los algoritmos, pero ¿realmente sabes cómo se las arregla para lucirse?

Aquí está la jugada: estamos bailando a través de cada elemento de una colección, preguntando si el elemento que estamos buscando es el que tenemos frente a nosotros. ¿El gran jefe de JavaScript que usa este algoritmo? ¡El método indexOf, pibe!

function indexOf(arr: number[], target: number): number {
	// Itera sobre cada elemento en el array
	for (let i = 0; i < arr.length; i++) {

		// Comprueba si el elemento actual es igual al objetivo
		if (arr[i] === target) {

			// Si lo es, devuelve el índice del elemento
			return i;
		}
	}

	// Si el objetivo no aparece por ningún lado, devuelve -1
	return -1;
}

Entonces... ¿cuál es el peor escenario aquí que nos dará la Notación Big O? Que volvamos con las manos vacías o que el elemento que buscamos esté paseando al final del array, haciendo que este algoritmo sea O(N). A medida que N crece, también lo hace la complejidad, es como ver tu cintura después de devorar una montaña de alfajores.

Búsqueda Binaria

Ahora, este es el rey de reyes, el mejor de los mejores y uno de los titanes en entrevistas profesionales y desafíos de programación. Veamos cuándo y cómo soltar su poder:

¿El truco? ¡Dividir y conquistar, che! En lugar de jugar al escondite con cada elemento del array, cortamos esa cosa en dos y preguntamos, "¿Eh, estás a la izquierda o a la derecha?" Luego, seguimos cortando hasta que atrapemos a nuestro esquivo objetivo.

function binarySearch(arr: number[], target: number): number {
	// Inicializa los punteros izquierdo y derecho
	// izquierdo comienza al principio del array
	// derecho comienza al final del array
	let left = 0;
	let right = arr.length - 1;

	// Continúa avanzando mientras el puntero izquierdo sea menor o igual al puntero derecho
	while (left <= right) {
		// Calcula el índice medio del espacio de búsqueda actual
		const mid = Math.floor((left + right) / 2);

		// Comprueba si el elemento medio es el objetivo
		if (arr[mid] === target) {

			// Si lo es, devuelve el índice del elemento
			return mid;
		} else if (arr[mid] < target) {

			// Si el elemento medio es menor que el objetivo, ve hacia la derecha
			left = mid + 1;
		} else {

			// Si el elemento medio es mayor que el objetivo, ve hacia la izquierda
			right = mid - 1;
		}
	}
}

Y con este ejemplo verás, claro como una luz que nos guia en las noches más oscuras, que no estoy mintiendo:

// necesitamos encontrar el índice del número objetivo dentro de un array de 1024 elementos

1024 / 2 = 512 // lo dividimos a la mitad y vemos que el número objetivo está en la mitad derecha
512 / 2 = 256 // lo dividimos a la mitad nuevamente y vemos que el número objetivo está en la mitad derecha
256 / 2 = 128 // lo dividimos a la mitad nuevamente y vemos que el número objetivo está en la mitad derecha
128 / 2 = 64 // lo dividimos a la mitad nuevamente y vemos que el número objetivo está en la mitad derecha
64 / 2 = 32 // lo dividimos a la mitad nuevamente y vemos que el número objetivo está en la mitad derecha
32 / 2 = 16 // lo dividimos a la mitad nuevamente y vemos que el número objetivo está en la mitad derecha
16 / 2 = 8 // lo dividimos a la mitad nuevamente y vemos que el número objetivo está en la mitad derecha
8 / 2 = 4 // lo dividimos a la mitad nuevamente y vemos que el número objetivo está en la mitad derecha
4 / 2 = 2 // lo dividimos a la mitad nuevamente y vemos que el número objetivo está en la mitad derecha
2 / 2 = 1 // lo dividimos a la mitad nuevamente y vemos que el número objetivo está en la mitad derecha
1 / 2 = 0.5 // ya no podemos dividirlo más, así que nos detenemos

// aquí viene la magia, si contamos el número de pasos tenemos un total de 10 pasos para encontrar el número objetivo
// ¿sabes cuál es el logaritmo de 1024 en base 2? ¡es 10!
log2(1024) = 10

Ejercicio de la bola de cristal

El problema de la bola cristal es un problema matemático clásico que se toma en entrevistas de programción. Se trata de encontrar la posición en la que dos bolas cristales se encuentran y se rompen al caer de una determinada altura. Lo importante aquí no es saber que son bolas de cristal, de que caen de una altura o cualquier otro detalle, tenemos que entender las bases y generalizar para que funcione en cualquier caso. Si realizamos esta tarea, podremos decir que la altura en verdad es un arreglo de n elementos, siendo 0 el inicio de la caida, n la altura máxima y index el lugar donde chocan las bolas.

// f = no se encuentran, t = se encuentran o se han encontrado previamente
const altura = [f, f, f, f, f, f, t, t, t, t, t];
//             inicio            choque        fin de la caida

Solución

Veamos las herramientas que ya disponemos de para resolver este problema:

  • Arrays: Arrays son una estructura de datos que contiene un conjunto de elementos de un mismo tipo. En este caso, la altura de las bolas.
  • Loop: Loop es una estructura de control que permite repetir una sección de código un número de veces. En este caso, el número de veces que se deben repetir es el número de elementos en el arreglo.
  • If: If es una estructura de control que permite ejecutar una sección de código si una condición es verdadera. En este caso, la condición es si el elemento en el arreglo es verdadero o falso.
  • Linear Search: Linear Search es una técnica de búsqueda en el que se busca un elemento en un arreglo mediante la búsqueda lineal, buscando el elemento en cada posición del arreglo y así sucesivamente.
  • Binary Search: Binary Search es una técnica de búsqueda en el que se busca un elemento en un arreglo mediante la búsqueda binaria, particionando .el arreglo en dos partes y buscando el elemento en la parte qué más se adecúe a lo que estamos buscando y así sucesivamente.
// Búsqueda lineal
const altura = [f, f, f, f, f, f, t, t, t, t, t];

function findCrystalBall(altura: number[]): number {
  for (let i = 0; i < altura.length; i++) {
    if (altura[i] === true) {
      return i;
    }
  }

  return -1;
}

El problema con esta solución es que no se puede optimizar para que funcione en cualquier caso, ya que la búsqueda lineal busca en cada posición del arreglo y así sucesivamente, lo que significa que si el arreglo tiene muchos elementos, el tiempo de ejecución será muy grande.

Así que vamos a buscar una solución más eficiente.

// Búsqueda binaria
function findCrystalBall(altura: number[]): number {
  let inicio = 0;
  let fin = altura.length - 1;

  while (inicio <= fin) {
    const index = Math.floor((inicio + fin) / 2);

    if (altura[index] === true) {
      return index;
    } else if (altura[index] === false) {
      inicio = index + 1;
    } else {
      fin = index - 1;
    }
  }

  return -1;
}

Funciona ? la verdad que no ! porque no estamos encontrando el momento justo en el que las bolas se encuentran, sino que estamos retornando el primer true que encontramos en vez del primero de todos. Además de esto, si sumamos la condición de que una vez que una de las bolas se rompa, ya no podrá volver a utilizarse, el tiempo de ejecución se mantendrá linear con el tamaño del arreglo. Ya que el peor de los casos haremos 1/2 de la altura y si encontramos un true, tendremos que volver a la posición anterior y buscar cual es el punto de quiebre lo cual sigue siendo O().

Asi que vamos a combinar todo lo que aprendimos hasta ahora para implementar una solucion increible y mucho más eficiente:

1- Vamos a reducir el tamaño del corte para que en vez de la mitad del arreglo, sea la raiz de N, y de esta manera se reduce considerablemente el tiempo de ejecución.

2- Una vez que encontremos el primer true, vamos a volver al punto donde empieza la sección de corte SQRT()N) y buscamos el primer true que se encuentre de manera LINEAR.

function findCrystalBall(altura: number[]): number {
  const N = altura.length;
  const SQRT = Math.floor(Math.sqrt(N));

  // ahora vamos a reducir el tamaño del corte para que en vez de la mitad del arreglo, sea la raiz de N
  // y lo recorremos de manera LINEAR, raiz de N cada vez
  let i = SQRT;

  for (; i < N; i += SQRT) {
    if (altura[i] === true) {
      break;
    }
  }

  i -= SQRT;

  for (let j = 0; j < SQRT && i < N; i++, j++) {
    if (altura[i] === true) {
      return i;
    }
  }

  return -1;
}

// Búsqueda binaria
function findCrystalBall(altura: number[]): number {
  let inicio = 0;
  let fin = altura.length - 1;

  while (inicio <= fin) {
    const index = Math.floor((inicio + fin) / 2);

    // comprueba si el valor en la posicíon media es 'true' y
    // si es el primer 'true' del arreglo (el elemento anterior debe ser 'false' si index no es 0)
    if (altura[index] === true)
      if (index === 0 || altura[index - 1] === false) return index;
      else fin = index - 1;
    else inicio = index + 1;
  }

  return -1;
}

Aunque las dos soluciones funcionan y parecen efectivas, la búsqueda linear es más eficiente !

  • N = 1000 pasos
  • SQRT(N) = 100 pasos
  • log2(N) = 10 pasos

crystal-ball-algorithms

Bubble Sort

Sorting es una de las cosas que más hacemos en el día a día como programadores, PERO, mucha gente no sabe lo que realmente pasa y depende de las famosas funciones mágicas que son parte de todos los lenguajes de programación.

Aunque no lo crean, hacer sorting es una de las cosas más fáciles que podemos hacer ! y lo mejor es que es también uno de los algoritmos más cortos a escribir.

La idea principal del sorting por el método de burbujeo es que se recorrerá un arreglo, comparando cada elemento con el próximo, si el elemento es mayor que el próximo, se intercambiarán lugares. Lo importante a saber es que al final de la primera iteración, el elemento más grande se encontrará en el final del arreglo. Esto nos permite volver a iterar el arreglo para seguir ordenando el resto de elementos pero de una manera más eficiente, ya que no debemos incluir el último elemento del resultado de la anterior iteración y así se irá reduciendo la cantidad de elmentos ante cada pasada hasta que el arreglo sea ordenado.

cont unsortedArray = [3, 1, 4, 8, 2];

// primera iteración
// comparamos el primero con el segundo y los cambiamos
cont unsortedArray = [1, 3, 4, 8, 2];
// comparamos el segundo con el tercero y los dejamos
cont unsortedArray = [1, 3, 4, 8, 2];
// comparamos el tercero con el cuarto y los dejamos
cont unsortedArray = [1, 3, 4, 8, 2];
// comparamos el cuarto con el quinto y los cambiamos
cont unsortedArray = [1, 3, 4, 2, 8]; // queda el 8 al final, el número más grande

// segunda iteración donde excluimos el 8 y volvemos a iterar

// comparamos el primero con el segundo y los dejamos
cont unsortedArray = [1, 3, 4, 2];
// comparamos el segundo con el tercero y los dejamos
cont unsortedArray = [1, 3, 4, 2];
// comparamos el tercero con el cuarto y los cambiamos
cont unsortedArray = [1, 3, 2, 4]; // el 4 queda al final, el número más grande

// tercera iteración donde excluimos el 4 y volvemos a iterar

// comparamos el primero con el segundo y los dejamos
cont unsortedArray = [1, 3, 2];
// comparamos el segundo con el tercero y los cambiamos
cont unsortedArray = [1, 2, 3]; // el 3 queda al final, el número más grande

// cuarta iteración donde excluimos el 3 y volvemos a iterar

// comparamos el primero con el segundo y los dejamos
cont unsortedArray = [1, 2]; // FIN

Si nos fijamos podemos descubrir un patrón encubierto en el código, ante cada iteración el resultado es N - i, donde N es el tamaño del arreglo y i es el número de iteraciones que hemos realizado hasta ahora.

const unsortedArray = [3, 1, 4, 8, 2];

// primera iteración N - i = 4
// resultado de la primera iteración = [1, 3, 4, 2]

// segunda iteración N - i = 3
// resultado de la segunda iteración = [1, 3, 2 ]

// tercera iteración N - i = 2
// resultado de la tercera iteración = [1, 2]

Si generalizamos el patrón, podemos decir que el resultado final sería N - N + 1 ya que la forma generalizada de calcular la sumatoria de elementos de un arreglo es: ((N + 1) * N) / 2

Sumatoria entre 1 y 10 es 11
Sumatoria entre 2 y 9 es 11
Sumatoria entre 3 y 8 es 11
Sumatoria entre 4 y 7 es 11
.
.
.
Sumatoria entre 5 y 6 es 11
Por lo que podemos decir que N siendo 5 y N + 1 siendo 6 el resultado final sería
(6 + 1) \* 5 / 2 = 11

Ahora si generalizamos el patrón dentro de la Big O, podemos decir que:

1- N (N + 1) / 2
2- N (N + 1) // eliminamos constantes elevando todo a 2
3- N^2 + N
// en Big O removemos valores insignificantes, si hablamos de números MUY grandes,
// + N es un MUY chico en comparación
4- N^2

Quedando O (N^2) en Big O

Código

function bubbleSort(array: number[]): number[] {
  // definimos el tamaño del arreglo
  const N = array.length;

  // iteramos sobre el arreglo
  for (let i = 0; i < N; i++) {
    // iteramos sobre el arreglo
    for (let j = 0; j < N - 1 - i; j++) {
      if (array[j] > array[j + 1]) {
        // si es mayor, cambiamos el elemento
        const temp = array[j];

        // cambiamos el elemento con el siguiente
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }

  return array;
}