Algoritmos y notación asintótica

7 min readFeb 14, 2017

La semana pasada empezamos una nueva aventura… arrancamos con las clases de JavaScript en el nuevo programa de educación continua de Laboratoria. Un reto inspirador, con un equipo de lujo, y un grupo de alumnas dispuestas a comerse el mundo.

Con la sana intención de dar una base en principios de computación, para la primera semana se programaron los temas de algoritmos y notación asintótica.

Desde el principio tuve mis dudas sobre si sería una buena idea empezar el curso hablando de esto. Mi preocupación principal es que son temas complicados, teóricos, matemáticos, … que siendo realista asustan a la mayoría de coders, acostumbrados a problemas más mundanos del diseño y desarrollo web.

Llegó la hora y empezamos, y algunos de mis temores se convirtieron en realidad. Algunas alumnas siguieron todo, varias quedaron confundidas y muchas simplemente se perdieron, y quizás ahora se preguntan si era o no una buena idea apuntarse a este curso… se abre el baúl de los recuerdos en mi imaginación… incluso me acuerdo de mí mismo, hace años, cuando no conseguía entender algo y en la desesperación terminaba pensando que nunca lo iba a entender, que quizás programar no era para mí.

Ahora me toca decirles a todas las que se sientan así que se equivocan, que sí pueden. Lleva tiempo… pero se puede, y no pasa absolutamente nada por sentirse abrumada con este tema. Poco a poco irá tomando sentido. En este artículo trataré de resumir y aclarar los conceptos más importantes, con la intención de “desmitificar” un tema complejo y facilitar su digestión. Así que al grano…

¿Qué es un algoritmo?

La definición más general, es que un algoritmo es simplemente una secuencia de pasos, que seguidos de forma precisa producen un resultado predecible, y que son aplicables a problemas similares.

Una manera de explicarlo es con la metáfora de las recetas de cocina. Cada receta es un algoritmo, que contiene los pasos para preparar un plato. Si una persona conoce y ha seguido muchas recetas, tendrá a sus disposición un arsenal de “conocimiento” y “experiencia” que le permitirán atacar problemas nuevos, como por ejemplo tener que cocinar con las limitaciones de una cocina/despensa en particular y un número de comensales. De la misma forma, un programador que haya estudiado algoritmos comunes y cómo analizarlos, tendrá a su disposición una mayor caja de herramientas a la hora de enfrentar problemas lógicos, llevarlos a código y analizar su eficiencia.

Al final, quizás lo más importante es quedarse con la forma de pensar, lo que llamamos el pensamiento algorítmico, que es lo que nos permite visualizar soluciones descritas paso a paso. Como programadores nuestro trabajo consiste en escribir instrucciones para que una computadora pueda seguirlas “paso a paso” (valga la redundancia) y conseguir un resultado esperado.

Algorithmic thinking is a way of getting to a solution through the clear definition of the steps needed — nothing happens by magic.
[Algorithms] are instructions or rules that if followed precisely (whether by a person or a computer) leads to answers to both the original and similar problems.
Fuente: https://teachinglondoncomputing.org/resources/developing-computational-thinking/algorithmic-thinking/

Hasta ahora hemos hablado de algoritmos en términos generales, pero cómo se traducen estas “recetas” a mi código? En la cocina, si vamos a cocinar arroz, no tenemos que “inventar” una forma de hacerlo; no tenemos que experimentar para decidir qué tipo de recipiente usar, si freírlo, hervirlo, hornearlo, … por cuánto tiempo cocinarlo, … a lo que quiero llegar es que existe una “receta”, que ya ha sido “descubierta”, “probada” y “perfeccionada” a lo largo del tiempo por muchos expertos, a partir de la cual uno puede después “implementar” una solución concreta. En computación y programación pasa lo mismo, en muchas ocasiones tenemos que “cocinar” una función o lógica en nuestro código, y saber algoritmos comunes nos permite desarrollar soluciones de una manera más eficiente e informada.

Algunos ejemplos de algoritmos: Merge Sort, Quick Sort, Heap Sort, Integer factorization, …

Notación asintótica

Hemos quedado en que los algoritmos son secuencias de pasos que podemos seguir para solucionar problemas concretos. Pero no sólo eso, sino que también hemos dicho que son como “recetas”, y esto quiere decir que no son “cualquier” secuencia de pasos, sino una que has sido “probada” (funciona correctamente) y “perfeccionada” (es eficiente).

Este último punto, la eficiencia, nos lleva a la temible “notación asintótica”. Siendo un concepto teórico, no voy a entrar en los detalles matemáticos, eso lo pueden encontrar en los links al final, si no ver algunos ejemplos que puedan servir para ilustrar los conceptos en líneas generales.

En computación, la notación asintótica nos permite representar la complejidad, y por ende la eficiencia, de un algoritmo, de tal manera que podemos proyectar el aumento de operaciones requeridas al aumentar el tamaño de la entrada (input).

Desde este punto de vista, el algoritmo más eficiente posible sería aquel en el que el número de operaciones llevadas a cabo no varíe según crezca la entrada. Esto es lo que sería una función constante. Por ejemplo:

function (n) {
  return n;
}function (n) {
  return (n * n) + 2;
}function (n) {
  return 25;
}

En las funciones anteriores, el número de operaciones realizados es independiente del tamaño de la entrada (el trabajo realizado es el mismo para n = 1 que para n = 1000). Por esto, decimos que son constantes, y su Big O (O Grande) es O(1).

Ahora supongamos que nuestro algoritmo requiere un poco más de trabajo y nuestra lógica nos obliga a iterar sobre n:

// Imprime todos los enteros positivos hasta `n` incluido
function printN(n) {
  for (var i = 1; i <= n; i++) {
    console.log(i);
  }
}

En la función de arriba, el número de operaciones va a ir aumentando según aumente el valor de n. En este caso el aumento va a ser lineal, ya que el bloque principal de nuestro código se va a ejecutar una vez para cada iteración, y así n = 1 resulta en 1 operación y n = 1000 resulta en 1000 operaciones. Por ello, en notación asintótica diríamos que nuestro algoritmo tiene una O grande (Big O) de O(n). Si tuviéramos un algoritmo que hace la misma iteración dos veces (una después de otra), diríamos que es O(2n), y si la segunda iteración estuviera anidada entonces sería O(n^2) (n al cuadrado).

Ahora, imaginemos que nos piden escribir una función que sume todos los números enteros hasta n. A primer instancia, de forma intuitiva, uno podría implementar la función usando iteración:

function sumaDeEnteros(n) {
  var sum = 0;
  for (var i = 1; i <= n; i++) {
    sum += i;
  }
  return sum;
}

La función de arriba tiene una O Grande de O(n), es lineal, que no está mal, pero como siempre, existen muchas formas de solucionar el problema. En este caso hay una solución matemática que nos permite implementar la misma lógica de una forma más eficiente:

function sumaDeEnteros(n) {
  return n * (n + 1) / 2;
}

Nuestra nueva implementación de sumaDeEnteros() produce exactamente los mismos resultados que la anterior, pero tiene una O Grande de O(1), es constante, ya que el número de operaciones es siempre 1, independientemente del valor de n; es mucho más eficiente. En este caso, existía una “receta”, probablemente no obvia para la mayoría de los mortales (me incluyo), pero que el estudio de algoritmos nos ofrece. Además, la notación asintótica nos permite rápidamente entender las diferencias de escalabilidad con respecto al tamaño de la entrada.

Hasta ahora sólo hemos mencionado O(1) y O(n), pero de forma común veremos eficiencias de O(log(n)), O(n * log(n)) en algoritmos eficientes y O(n^2) (n al cuadrado) o mayores en algoritmos más complejos.

Notaciones comunes en orden de eficiencia:

O(1)
O(log(n))
O(n)
O(n * log(n))
O(n^2)
O(2^n)
…

Para poder “visualizar” cómo afecta el tamaño de la entrada al número de operaciones he creado una “gráfica interactiva” donde pueden comparar las curvas que producen las diferentes O Grandes (constante, lineal, logarítmica, polinomial, exponencial, …) al plotear n y las operaciones resultantes. Mi recomendación es empezar comparando las más eficientes, porque en cuanto añadimos la exponencial (menos eficiente) todas las demás curvas parecen planas, ya que la diferencia de crecimiento es enorme:

Para terminar esta sección, no olvidemos que la notación asintótica es una simplificación donde ignoramos un montón de factores y nos concentramos en el impacto que tiene el aumento del valor de entrada con respecto al número de operaciones que tendrá que ejecutar un algoritmo. Tengamos en cuenta que estamos ignorando lo que ocurre antes, durante y después de las iteraciones, que en este tipo de análisis se considera constante y al aumentar el valor de n lo suficiente se vuelve despreciable.

Ad-hoc

Los problemas Ad Hoc, son problemas de habilidad o de implementación que no requieren conocer un algoritmo en específico. Depende más de tus habilidades lógicas y se mejoran con la práctica. Así que lo único que añadir es: a practicar!

Resumen

Los algoritmos dan miedo, no te sientas sola, ese miedo pasa.
Un algoritmo es una secuencia de pasos, que seguidos de forma precisa, producen resultados predecibles para problemas tipificados.
El pensamiento algorítmico nos permite visualizar soluciones descritas paso a paso.
Los algoritmos son como recetas, secuencias paso a paso, probadas y perfeccionadas (eficientes).
Los programadores, como los chefs ganamos sabiendo más recetas.
La notación asintótica nos permite expresar la eficiencia de un algoritmo, de tal manera que podemos proyectar el aumento de operaciones requeridas al aumentar el tamaño de la entrada (input).

Ejercicios

Lecturas y videos complementarios: