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 | ||
algoritmos-oia:divide-and-conquer [2017/12/23 14:21] brianbok |
algoritmos-oia:divide-and-conquer [2018/01/22 14:32] (actual) 35.226.23.240 ↷ Links adapted because of a move operation |
||
---|---|---|---|
Línea 9: | Línea 9: | ||
====== Ejemplo: Merge Sort ====== | ====== Ejemplo: Merge Sort ====== | ||
- | En el algoritmo de [[algoritmos-oia:merge-sort|merge sort]] utilizamos la técnica de Divide & Conquer. | + | En el algoritmo de [[algoritmos-oia:ordenamiento:merge-sort|merge sort]] utilizamos la técnica de Divide & Conquer. |
* __Divide:__ Llamadas a sort de las dos mitades del arreglo | * __Divide:__ Llamadas a sort de las dos mitades del arreglo | ||
* __Conquer:__ Construcción del ordenamiento a partir de las dos mitades, etapa de merge | * __Conquer:__ Construcción del ordenamiento a partir de las dos mitades, etapa de merge | ||
Línea 17: | Línea 17: | ||
* Método de sustitución | * Método de sustitución | ||
* [[algoritmos-oia:teorema-maestro|Teorema maestro]] | * [[algoritmos-oia:teorema-maestro|Teorema maestro]] | ||
+ | |||
+ | ====== Ejemplos de algoritmos/problemas con D&C ====== | ||
+ | |||
+ | * Solución $O(n log n)$ a maximum subarray | ||
+ | * Karatsuba y Strassen | ||
+ | |||
+ | ====== Continuar leyendo ====== | ||
+ | * D&C sobre árboles | ||
+ | * Programación Dinámica | ||
+ | |||
+ |