Dividir e Conquistar
“Dividir e Conquistar” é uma técnica bastante utilizada para resolver problemas de algoritmos. Já vimos anteriormente algumas estratégias para abordar esses desafios. A abordagem gulosa (greedy approach) escolhe o resultado mais vantajoso em cada passo. A programação dinâmica (dynamic programming) constrói o estado atual com base nos anteriores. Já na estratégia de dividir e conquistar, separamos o problema em subproblemas menores e resolvemos cada um deles, combinando depois todos os resultados. Dessa forma, dividimos o problema em partes e conquistamos o problema inicial ao juntar as soluções dos subproblemas.
Desafio
Imagine que lhe são fornecidos 512 números e que existem 512 computadores especializados (pequenos e bastante específicos) capazes apenas de calcular e retornar o máximo entre dois números.
O objetivo é encontrar o valor máximo entre esses 512 números no menor tempo possível.
Cada um desses computadores recebe dois números e devolve o maior deles em 1 segundo (sim, são um pouco lentos 🐌). Consegue pensar num algoritmo que permita calcular o máximo de todos esses números o mais rapidamente possível?