logo

TechCodeview

Algorithme Diviser pour régner

Algorithme Diviser pour Régner est une stratégie de résolution de problèmes qui consiste à décomposer un problème complexe en parties plus petites et plus faciles à gérer, à résoudre chaque partie individuellement, puis à combiner les solutions pour résoudre le problème d'origine. Il s’agit d’une technique algorithmique largement utilisée en informatique et en mathématiques.

Exemple: Dans le Tri par fusion algorithme, le Diviser et conquérir la stratégie est utilisée pour trier une liste d’éléments. L'image ci-dessous illustre les états de division et de fusion pour trier le tableau en utilisant Tri par fusion .



Table des matières

Qu’est-ce que l’algorithme Diviser pour régner ?

Diviser pour mieux régner est une technique de résolution de problèmes qui consiste à diviser un problème plus vaste en sous-problèmes, à résoudre les sous-problèmes indépendamment et à combiner les solutions de ces sous-problèmes pour obtenir la solution du problème plus vaste.



Étapes de l’algorithme Diviser pour régner :

L’algorithme Divide and Conquer peut être divisé en trois étapes : Diviser , Conquérir et Fusionner .

1. Divisez :

  • Décomposez le problème initial en sous-problèmes plus petits.
  • Chaque sous-problème doit représenter une partie du problème global.
  • Le but est de diviser le problème jusqu’à ce qu’aucune autre division ne soit possible.

2. Conquérir :

  • Résolvez chacun des petits sous-problèmes individuellement.
  • Si un sous-problème est suffisamment petit (souvent appelé cas de base), nous le résolvons directement sans autre récursion.
  • L’objectif est de trouver des solutions à ces sous-problèmes de manière indépendante.

3. Fusionner :

  • Combinez les sous-problèmes pour obtenir la solution finale de l’ensemble du problème.
  • Une fois les petits sous-problèmes résolus, nous combinons récursivement leurs solutions pour obtenir la solution d’un problème plus vaste.
  • Le but est de formuler une solution au problème initial en fusionnant les résultats des sous-problèmes.

Applications de l’algorithme Diviser pour régner :

  • Tri par fusion: Le tri par fusion est un exemple classique d’algorithme de tri diviser pour régner. Il décompose le tableau en sous-tableaux plus petits, les trie individuellement, puis les fusionne pour obtenir le tableau trié.
  • Résultat médian : La médiane d’un ensemble de nombres peut être trouvée en utilisant une approche diviser pour mieux régner. En divisant récursivement l’ensemble en sous-ensembles plus petits, la médiane peut être déterminée efficacement.
  • Résultat Min et Max : L'algorithme Divide and Conquer peut être utilisé pour rechercher simultanément les éléments minimum et maximum dans un tableau. En divisant le tableau en moitiés et en comparant les paires min-max de chaque moitié, le min et le max globaux peuvent être identifiés en complexité temporelle logarithmique.
  • Multiplication matricielle : L'algorithme de Strassen pour la multiplication matricielle est une technique de division pour mieux régner qui réduit le nombre de multiplications requises pour les grandes matrices en décomposant les matrices en sous-matrices plus petites et en combinant leurs produits.
  • Problème de paire la plus proche : Le problème des paires les plus proches consiste à trouver les deux points les plus proches dans un ensemble de points dans un espace multidimensionnel. Un algorithme diviser pour régner, tel que l'algorithme diviser pour régner des paires les plus proches, peut résoudre efficacement ce problème en divisant les points de manière récursive et en fusionnant les solutions des sous-problèmes.

Bases de l’algorithme Diviser pour régner :

Algorithmes standards sur Algorithme Diviser pour régner :

  • Recherche binaire
  • Tri par fusion
  • Tri rapide
  • Calculer puissance (x, n)
  • Algorithme Karatsuba pour une multiplication rapide
  • Multiplication matricielle de Strassen
  • Coque convexe (algorithme simple de division et de conquête)
  • Algorithme Quickhull pour coque convexe

Problèmes liés à la recherche binaire :

  • Trouver un élément de pointe dans un tableau donné
  • Rechercher un élément majoritaire dans un tableau trié
  • K-ième élément de deux tableaux triés
  • Trouver le nombre de zéros
  • Trouver le nombre de rotations dans le tableau trié avec rotation
  • Trouver le point où une fonction croissante de manière monotone devient positive pour la première fois
  • Médiane de deux tableaux triés
  • Médiane de deux tableaux triés de tailles différentes
  • Le problème de partition du peintre à l'aide de la recherche binaire

Pratiquez des problèmes sur Algorithme Diviser pour régner :

  • Racine carrée d'un entier
  • Maximum et minimum d'un tableau utilisant un nombre minimum de comparaisons
  • Trouver la fréquence de chaque élément dans un tableau à plage limitée en moins d'un temps O(n)
  • Problème de carrelage
  • Compter les inversions
  • Le problème de la ligne d'horizon
  • Rechercher dans un tableau 2D trié par lignes et par colonnes
  • Allouer un nombre minimum de pages
  • Exponentiation modulaire (puissance en arithmétique modulaire)

Liens rapides :

  • Apprendre la structure des données et les algorithmes | Tutoriel DSA
  • « Problèmes de pratique » sur Diviser pour régner
  • « Quiz » sur Diviser pour régner