Neste tutorial, você aprenderá como funciona o algoritmo de divisão e conquista. Também compararemos a abordagem de dividir e conquistar com outras abordagens para resolver um problema recursivo.
Um algoritmo de divisão para conquistar é uma estratégia de resolver um grande problema por
- dividindo o problema em subproblemas menores
- resolvendo os subproblemas, e
- combinando-os para obter a saída desejada.
Para usar o algoritmo de divisão e conquista, recursão é usada. Saiba mais sobre recursão em diferentes linguagens de programação:
- Recursão em Java
- Recursão em Python
- Recursão em C ++
Como funcionam os algoritmos de divisão e conquista?
Aqui estão as etapas envolvidas:
- Divide : Divide o problema fornecido em subproblemas usando recursão.
- Conquistar : Resolva os subproblemas menores recursivamente. Se o subproblema for pequeno o suficiente, resolva-o diretamente.
- Combine: Combine as soluções dos subproblemas que fazem parte do processo recursivo para resolver o problema real.
Vamos entender este conceito com a ajuda de um exemplo.
Aqui, classificaremos um array usando a abordagem de divisão e conquista (ou seja, classificação por mesclagem).
- Deixe o array fornecido ser:
Array for merge sort - Divida a matriz em duas metades.
Divida a matriz em duas subpartes
Novamente, divida cada subparte recursivamente em duas metades até obter os elementos individuais.
Divida a matriz em subpartes menores - Agora, combine os elementos individuais de uma maneira ordenada. Aqui, conquistar e combinar etapas caminham lado a lado.
Combine as subpartes
Complexidade de tempo
A complexidade do algoritmo de dividir e conquistar é calculada usando o teorema mestre.
T (n) = aT (n / b) + f (n), onde, n = tamanho da entrada a = número de subproblemas na recursão n / b = tamanho de cada subproblema. Todos os subproblemas são considerados como tendo o mesmo tamanho. f (n) = custo do trabalho realizado fora da chamada recursiva, que inclui o custo de dividir o problema e o custo de mesclar as soluções
Tomemos um exemplo para encontrar a complexidade de tempo de um problema recursivo.
Para uma classificação por mesclagem, a equação pode ser escrita como:
T (n) = aT (n / b) + f (n) = 2T (n / 2) + O (n) Onde, a = 2 (cada vez, um problema é dividido em 2 subproblemas) n / b = n / 2 (tamanho de cada subproblema é a metade da entrada) f (n) = tempo gasto para dividir o problema e mesclar os subproblemas T (n / 2) = O (n log n) (Para entender isso, consulte o teorema mestre.) Agora, T (n) = 2T (n log n) + O (n) ≈ O (n log n)
Abordagem Dividir e Conquistar Vs Dinâmica
A abordagem de dividir para conquistar divide um problema em subproblemas menores; esses subproblemas são resolvidos recursivamente. O resultado de cada subproblema não é armazenado para referência futura, enquanto, em uma abordagem dinâmica, o resultado de cada subproblema é armazenado para referência futura.
Use a abordagem de dividir para conquistar quando o mesmo subproblema não for resolvido várias vezes. Use a abordagem dinâmica quando o resultado de um subproblema for usado várias vezes no futuro.
Vamos entender isso com um exemplo. Suponha que estejamos tentando encontrar a série Fibonacci. Então,
Abordagem de dividir e conquistar:
fib (n) Se n <2, retorna 1 Caso contrário, retorna f (n - 1) + f (n -2)
Abordagem dinâmica:
mem = () fib (n) Se n em mem: retorna mem (n) else, Se n <2, f = 1 else, f = f (n - 1) + f (n -2) mem (n) = f return f
Em uma abordagem dinâmica, mem armazena o resultado de cada subproblema.
Vantagens de dividir e conquistar o algoritmo
- A complexidade para a multiplicação de duas matrizes usando o método ingênuo é O (n 3 ), enquanto usando a abordagem dividir para conquistar (ou seja, a multiplicação da matriz de Strassen) é O (n 2,8074 ). Essa abordagem também simplifica outros problemas, como a Torre de Hanói.
- Essa abordagem é adequada para sistemas de multiprocessamento.
- Faz uso eficiente de caches de memória.
Divida e conquiste aplicativos
- Pesquisa Binária
- Mesclar Classificar
- Ordenação rápida
- Multiplicação da matriz de Strassen
- Algoritmo Karatsuba
