El O(N logN) de los humildes: clase de sqrt decomposition.

[marianocr...@gmail.com]

Voy a dar un conjunto de técnicas muy útiles en el diseño de algoritmos que permite transformar muchos algoritmos O(N^2) en O(sqrt(N)*N).

En la práctica, iguala la performance de muchos algoritmos O(N logN) por lo que también se lo llama el "N log N del humilde".

Es un tema muy importante porque se puede usar para resolver una gran gran variedad de problemas. Incluso muchos que no fueron pensados para ser resueltos utilizando este truco.

CUANDO? Miércoles 09/10 a las 19.15. Arranca puntual
DONDE? 5to piso UTN (Zeballos 1341), laboratorio de redes

Más detalle de las técnicas que vamos a ver:
• Combinar dos algoritmos O(n^2/k) y O(n*k) garantizando O(n sqrt(n))
• Procesar n elementos de a grupos de k_i con dos algoritmos O(k_i^2) o O(n) garantizando O(n sqrt(n)).
• Procesar Q queries que se pueden resolver en O(len(queries anteriores)^2) garantizando O(n sqrt(n)).
• Dividir la entrada en bloques de sqrt(N) para responder Q consultas en O(sqrt(N)*Q)
• Mo's Algorithm
Lo importante es que vamos a ver muchos ejemplos, que es lo fundamental para poder detectar cuándo se puede aplicar la técnica.

Los espero,
Mariano