Big O sin la matemática pesada
Seguí leyendo
Enterate del próximo post
Un mail cuando publico algo nuevo. Sin spam y te podés dar de baja cuando quieras.
Un mail cuando publico algo nuevo. Sin spam y te podés dar de baja cuando quieras.
Organizar una fiesta tiene tareas que crecen de maneras muy distintas cuando crece la lista de invitados. Mandar un único mensaje al grupo con la dirección cuesta lo mismo con diez invitados que con cien. Entregar las invitaciones en mano lleva una visita por invitado: con el doble de gente, el doble de visitas. Y si todos tienen que saludarse con todos, cada invitado nuevo saluda a cada uno de los que ya estaban: con diez personas hay 45 saludos, y con veinte, 190.
El post anterior encontró esas mismas tres formas de crecer en algoritmos concretos, contando sus pasos uno por uno. Contar así funciona, pero es tedioso y depende de detalles que no cambian la conclusión, como si se cuenta o no la asignación inicial. Este post presenta una notación que se queda solo con lo que importa: la forma en que crece la cuenta.
La notación Big O (se lee "o grande") describe cómo crece la cantidad de pasos de un algoritmo en función del tamaño de su entrada. Por convención, ese tamaño se llama n: la cantidad de elementos de una lista, la cantidad de invitados, el número que recibe sumar_primeros. Se escribe O(...) con la forma de crecimiento adentro, y se lee "del orden de".
Para pasar de una cuenta exacta a su Big O alcanzan dos reglas.
La primera: se descartan las constantes. Un algoritmo que siempre hace 4 pasos, sin importar n, es O(1): la cuenta no crece. Uno que hace 3n + 2 pasos es O(n), igual que uno que hace exactamente n. El 3 y el 2 dependen de qué se decidió contar y de cómo se escribió el algoritmo; la forma de crecer no. En los dos casos, duplicar la entrada duplica, aproximadamente, la cantidad de pasos.
La segunda: se conserva solo el término que crece más rápido. Comparar todos los pares de una lista hace n × (n - 1) / 2 comparaciones, que es la mitad de n² menos la mitad de n. Con n en 1000, el primer término vale 500000 y el segundo, 500. A medida que n crece, el término menor pesa cada vez menos en el total, así que la cuenta completa se resume como O(n²).
Con esas dos reglas, Big O responde una pregunta práctica sin ninguna fórmula: qué pasa con la cantidad de pasos si la entrada se duplica. En un algoritmo O(1), nada. En uno O(n), se duplica. En uno O(n²), se multiplica por cuatro, porque el doble por el doble da cuatro veces más.
Como en el post anterior, lo habitual es describir el peor caso: Big O funciona como una garantía de que ninguna entrada de ese tamaño va a hacer crecer la cuenta más rápido. Y conviene tener presente lo que Big O no dice: no dice qué algoritmo es más rápido con entradas chicas. suma_directa es O(1) y sumar_primeros es O(n), y aun así el segundo hace menos operaciones con cantidad en 1, 2 o 3. Big O habla de la tendencia, no de un caso puntual.
Existen otras formas de crecer además de estas tres. Dos de ellas aparecen en el bloque siguiente, con los algoritmos de búsqueda y de ordenamiento que las producen, y se presentan recién ahí.
Los tres algoritmos del post anterior, clasificados con las dos reglas:
suma_directa hace siempre 4 operaciones. No depende de n: O(1).esta_en_stock, en el peor caso, hace una comparación por elemento: n comparaciones, O(n).repetidos_por_pares compara la primera posición con las n - 1 siguientes, la segunda con las n - 2 siguientes, y así hasta la última pareja. En total, n × (n - 1) / 2 comparaciones: O(n²).La pregunta de la duplicación se puede comprobar con números reales, tomando el peor caso de cada uno:
| n | suma_directa | esta_en_stock | repetidos_por_pares |
|---|---|---|---|
| 1000 | 4 | 1000 | 499500 |
| 2000 | 4 | 2000 | 1999000 |
| 4000 | 4 | 4000 | 7998000 |
Cada vez que n se duplica, la primera columna no cambia, la segunda se duplica y la tercera se multiplica casi exactamente por cuatro. No hizo falta conocer ninguna de esas cifras de antemano para anticiparlo: alcanzaba con saber que el primero es O(1), el segundo O(n) y el tercero O(n²).
Determinar el Big O del siguiente algoritmo, que calcula la diferencia entre la venta más alta y la más baja del día, recorriendo la lista dos veces.
Pista: un bucle puesto después de otro no se comporta igual que un bucle puesto adentro de otro. Contar cuántas comparaciones hace cada recorrido, sumarlas, y aplicar la primera regla.
algoritmo rango_de_ventas(ventas):
asignar el elemento en la posición 1 de ventas a minima
asignar el elemento en la posición 1 de ventas a maxima
repetir contador desde 2 hasta la cantidad de elementos de ventas:
si el elemento en la posición contador de ventas es menor a minima:
asignar el elemento en la posición contador de ventas a minima
repetir contador desde 2 hasta la cantidad de elementos de ventas:
si el elemento en la posición contador de ventas es mayor a maxima:
asignar el elemento en la posición contador de ventas a maxima
asignar maxima a rango
restar minima a rango
devolver rangoCon ventas en [4500, 3200, 6000, 2800, 5100], el primer bucle deja minima en 2800, el segundo deja maxima en 6000, y el resultado es 3200. Cada bucle hace n - 1 comparaciones, así que en total son 2 × (n - 1): 8 con estas cinco ventas, 1998 con mil. Por la primera regla, el 2 y el 1 se descartan, y el algoritmo es O(n). Duplicar la lista duplica el trabajo, no lo cuadruplica: los dos recorridos se suman, no se multiplican. Lo que produce O(n²) en repetidos_por_pares es que el bucle interno se repite completo por cada vuelta del externo.
Un torneo de barrio se juega todos contra todos: cada equipo enfrenta una vez a cada uno de los demás. Hace falta un algoritmo que reciba la lista de equipos y devuelva la lista de partidos, y saber qué pasa con su trabajo si el año próximo se anota el doble de equipos.
Pista: cada partido es una pareja de equipos distintos, sin repetir la misma pareja al revés. Antes de buscar un algoritmo más rápido, conviene preguntarse cuántos partidos tiene que devolver.
algoritmo armar_fixture(equipos):
asignar una lista vacía a partidos
asignar la cantidad de elementos de equipos a ultima
restar 1 a ultima
repetir local desde 1 hasta ultima:
asignar local a inicio
sumar 1 a inicio
repetir visitante desde inicio hasta la cantidad de elementos de equipos:
asignar el resultado de unir el elemento en la posición local de equipos, " contra " y el elemento en la posición visitante de equipos a partido
agregar partido al final de partidos
devolver partidosCon equipos en ["Norte", "Sur", "Este", "Oeste"], el resultado tiene 6 partidos: "Norte contra Sur", "Norte contra Este", "Norte contra Oeste", "Sur contra Este", "Sur contra Oeste" y "Este contra Oeste". Es la misma estructura de bucles que repetidos_por_pares, así que hace n × (n - 1) / 2 vueltas y es O(n²): con 8 equipos arma 28 partidos, con 16 arma 120 y con 32 arma 496. Duplicar los equipos multiplica el trabajo por algo más de cuatro con números chicos, y por casi exactamente cuatro a medida que crecen.
La diferencia con repetidos_por_pares está en la pista. Ahí existía una versión O(n) con un conjunto, porque la respuesta era un solo valor verdadero o falso. Acá la respuesta misma es una lista de n × (n - 1) / 2 partidos, y ningún algoritmo puede devolverla sin armar cada uno. Cuando el resultado tiene ese tamaño, O(n²) no es un defecto del algoritmo: es el piso del problema.
Big O resume una cuenta de pasos en su forma de crecer: se descartan las constantes y se conserva solo el término que crece más rápido. Lo que dice en la práctica es qué pasa si la entrada se duplica: nada en O(1), el doble en O(n), cuatro veces más en O(n²). No dice qué algoritmo gana con entradas chicas, y a veces la forma de crecer la impone el problema y no el algoritmo.
El próximo post vuelve sobre el conjunto que hizo O(n) la búsqueda de repetidos: ese tiempo ganado se pagó con memoria, y ese intercambio entre espacio y tiempo, junto con el riesgo de optimizar antes de que haga falta, es su tema.