Dividir para conquistar é uma estratégia para projetar algoritmos assintoticamente eficientes. A estratégia se baseia na ideia de que, ao invés de resolver um problema diretamente, podemos dividi-lo recursivamente em subproblemas menores e de mesma estrutura até que os subproblemas sejam tão pequenos que possam ser resolvidos diretamente e então combinar os resultados para obter a solução do problema original.
Sendo assim, o funcionamento da estratégia de dividir para conquistar se dá através dos seguintes passos:
- Dividir o problema original em subproblemas de mesma estrutura mas menor tamanho que o original.
- Conquistar os subproblemas resolvendo-os recursivamente. Caso o subproblema seja simples o bastante, ele será resolvido diretamente, caso contrário ele será dividido em mais subproblemas.
- Combinar as soluções dos subproblemas na solução do problema original.
Exemplos de algoritmos que utilizam a técnica de dividir para conquistar incluem:
É possível analisar a complexidade de algoritmos que utilizam da estratégia de dividir para conquistar através da análise de árvores de recursão ou através da aplicação do Teorema mestre.