Diviser pour mieux régner au milieu

Certains problèmes ont un N proche de 40, et essayer les 2^N sous-ensembles est irréalisable. La méthode des deux moitiés permet de résoudre ces cas de taille intermédiaire. 🤝

Divisez l’entrée en deux moitiés. Résolvez chaque moitié par force brute, puis combinez astucieusement les deux résultats partiels.

Deux moitiés de taille N/2 coûtent chacune 2^(N/2), au lieu de 2^N au total. Cette réduction par racine carrée transforme 2^40 en une valeur raisonnable de 2^20.

Déterminez si un sous-ensemble a une somme égale à une cible T. La somme de sous-ensemble avec un N proche de 40 est le problème classique de la méthode des deux moitiés.

Énumérez toutes les sommes de sous-ensembles de la moitié gauche et stockez-les. Avec N/2 éléments, cela représente simplement 2^(N/2) sommes.

Faites de même pour la moitié droite et construisez la liste complète de ses sommes de sous-ensembles. Vous disposez maintenant de deux listes faciles à gérer.

Pour chaque somme droite r, vous avez besoin d’une somme gauche égale à T moins r. Un ensemble ou une liste triée permet de vérifier cela rapidement.

Pour des cibles exactes, utilisez un ensemble de hachage. Pour compter ou trouver les sommes les plus proches, triez une moitié et effectuez une recherche dichotomique.

Le travail total est d’environ 2^(N/2) multiplié par un facteur logarithmique pour la recherche ou le tri. C’est cette complexité qui rend un N proche de 40 réalisable.

Vous stockez une moitié complète, donc la mémoire augmente jusqu’à 2^(N/2). Ne conservez que ce qui est nécessaire pour respecter la limite.

Au-delà de la somme de sous-ensembles, utilisez cette méthode pour le sous-ensemble maximal sous une limite, le comptage de paires et les problèmes de type logarithme discret. Elle apprécie une séparation bien choisie.

Vous appliquez la méthode des deux moitiés à un problème de sous-ensemble contenant N éléments. Quel est le coût temporel approximatif ?

Divisez en deux moitiés, effectuez une recherche exhaustive dans chacune, puis faites correspondre les sommes gauche et droite. Vous avez échangé un peu de mémoire contre une énorme accélération. 🚀