Herramientas de usuario
brainstorm:brainstorm-metaideas
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-metaideas [2018/03/24 21:22] santo |
brainstorm:brainstorm-metaideas [2019/08/15 11:15] (actual) santo |
||
|---|---|---|---|
| Línea 4: | Línea 4: | ||
| * Heurística de conjunto-ordenación | * Heurística de conjunto-ordenación | ||
| + | * Heurística de queries que "dividan parejo" el espacio de opciones [para problemas de teoría de información, golosa "generalmente buena" pero no óptima] | ||
| * "Dar vuelta el sentido de la recursión", si eso ayuda en algo (puede pasar de no salir a salir. También es clave cuando hay que dar el i-ésimo lexicográfico). | * "Dar vuelta el sentido de la recursión", si eso ayuda en algo (puede pasar de no salir a salir. También es clave cuando hay que dar el i-ésimo lexicográfico). | ||
| * "Idea china del binomial heap" (transforma un algoritmo para el problema estático, en un algoritmo para el problema dinámico con un overhead logarítmico) | * "Idea china del binomial heap" (transforma un algoritmo para el problema estático, en un algoritmo para el problema dinámico con un overhead logarítmico) | ||
| Línea 10: | Línea 11: | ||
| * Reducciones entre problemas: "Desde el nuestro" (para resolverlo, haciéndolo más fácil que uno conocido) y "Hacia el nuestro" (para pensar cómo encararlo y cómo *no* encararlo, al concluir que es al menos tan difícil como algo conocido. Ejemplo, "este va a necesitar sí o sí un segment tree, o algo más difícil" o bien "Este problema es al menos tan difícil como este otro, que yo ya sé que no me sale") | * Reducciones entre problemas: "Desde el nuestro" (para resolverlo, haciéndolo más fácil que uno conocido) y "Hacia el nuestro" (para pensar cómo encararlo y cómo *no* encararlo, al concluir que es al menos tan difícil como algo conocido. Ejemplo, "este va a necesitar sí o sí un segment tree, o algo más difícil" o bien "Este problema es al menos tan difícil como este otro, que yo ya sé que no me sale") | ||
| * "Subalgorithms": En definitiva es separar en casos el problema, y resolver cada caso con algoritmos bien distintos. Pero la división en casos puede no tener nada que ver con "la respuesta" que es más común, sino con "el tiempo" de ejecución. Los ejemplos típicos son problemas donde ocurre algo de esta pinta: uno tiene que procesar todos los $k$ de $1$ hasta $N$, y para procesar cada uno, existen dos métodos (uno tiene que descubrir todo esto para el problema puntual, obviamente :P): Uno procesa en $O(k)$, y el otro en $O(\frac{N}{k})$. Los dos métodos son lineales en $N$ en peor caso, así que la complejidad total queda cuadrática. Pero si usamos uno para los valores chicos y otro para los grandes, procesar se hace siempre en $O(\sqrt{N})$, y el total del algoritmo pasa a ser $O(N \sqrt{N})$. | * "Subalgorithms": En definitiva es separar en casos el problema, y resolver cada caso con algoritmos bien distintos. Pero la división en casos puede no tener nada que ver con "la respuesta" que es más común, sino con "el tiempo" de ejecución. Los ejemplos típicos son problemas donde ocurre algo de esta pinta: uno tiene que procesar todos los $k$ de $1$ hasta $N$, y para procesar cada uno, existen dos métodos (uno tiene que descubrir todo esto para el problema puntual, obviamente :P): Uno procesa en $O(k)$, y el otro en $O(\frac{N}{k})$. Los dos métodos son lineales en $N$ en peor caso, así que la complejidad total queda cuadrática. Pero si usamos uno para los valores chicos y otro para los grandes, procesar se hace siempre en $O(\sqrt{N})$, y el total del algoritmo pasa a ser $O(N \sqrt{N})$. | ||
| + | * flujo / corte / conservación / mover cosas de un lado a otro. Ejemplo feliz especial: "en un camino" (Arte Moderno, Toneles, Railroads). | ||
brainstorm/brainstorm-metaideas.1521926558.txt.gz · Última modificación: 2018/03/24 21: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
