Herramientas de usuario
brainstorm:brainstorm-algoritmos
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa | ||
|
brainstorm:brainstorm-algoritmos [2019/03/04 22:22] santo |
brainstorm:brainstorm-algoritmos [2019/09/08 17:35] (actual) santo |
||
|---|---|---|---|
| Línea 183: | Línea 183: | ||
| * Dualidad intervalo - punto ([A,B] -- (A,B) , complementar intervalos es reflejar por y=x (caso circular)) | * Dualidad intervalo - punto ([A,B] -- (A,B) , complementar intervalos es reflejar por y=x (caso circular)) | ||
| * Truquito de la f lineal que transforma norma 1 en norma infinito (en 2D es "rotar 45") | * Truquito de la f lineal que transforma norma 1 en norma infinito (en 2D es "rotar 45") | ||
| + | * Hay O(NM) rectángulos maximales en una grilla de NxM (Implica O(T^2) para T obstáculos), y cómo enumerarlos (desde cada casilla tirar un rayito para abajo, y de donde pega, expandir para los costados. Eso pasa por todos los maximales y por algunos no maximales [y posiblemente varias veces]) | ||
| * Divide and conquer | * Divide and conquer | ||
| * Par de puntos mas cercano en O(n lg n) | * Par de puntos mas cercano en O(n lg n) | ||
| Línea 188: | Línea 189: | ||
| * Karatsuba | * Karatsuba | ||
| * Armado de fixtures (aunque hay una alternativa constructiva muy elegante y simple) | * Armado de fixtures (aunque hay una alternativa constructiva muy elegante y simple) | ||
| - | * Elemento mayoría (y solución lineal) | + | * Elemento mayoría (y solución lineal, con O(1) memoria, o alternativamente con 3/2N comparaciones) |
| * Meet in the middle | * Meet in the middle | ||
| * BFS (tipo cubo de Rubik) | * BFS (tipo cubo de Rubik) | ||
brainstorm/brainstorm-algoritmos.1551738120.txt.gz · Última modificación: 2019/03/04 22:22 por santo
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
