Divide and Conquer (Diviser pour régner)
Divide and Conquer est une technique très répandue pour résoudre des problèmes d’algorithmique. Nous avons déjà exploré plusieurs approches pour ce genre de tâches : la méthode gloutonne (greedy) choisit la meilleure option à chaque étape, tandis que la programmation dynamique (dynamic programming) construit l’état courant à partir des résultats précédents. Avec la méthode de "divide and conquer", on découpe le problème en sous-problèmes plus petits, qu’on résout individuellement, puis on combine les résultats finaux. Autrement dit, on divise le problème en sous-problèmes et on conquiert le problème initial en rassemblant les solutions de ces sous-problèmes.
Challenge
Imaginez que l’on vous donne 512 nombres, et que vous disposiez de 512 ordinateurs spécialisés (de très petits dispositifs spécialisés), chacun étant capable uniquement de calculer et de renvoyer le maximum de deux nombres.
Vous souhaitez obtenir le maximum parmi ces 512 nombres le plus rapidement possible.
Chaque ordinateur reçoit deux nombres et renvoie le maximum entre eux en 1 seconde (eh oui, ils sont un peu lents 🐌). Pourriez-vous imaginer un algorithme permettant de trouver le maximum de tous ces nombres aussi vite que possible ?