logo

TechCodeview

Algoritme Divideix i Conquista

Algorisme Divide and Conquer és una estratègia de resolució de problemes que consisteix a desglossar un problema complex en parts més petites i manejables, resolent cada part individualment i després combinar les solucions per resoldre el problema original. És una tècnica algorítmica molt utilitzada en informàtica i matemàtiques.

Exemple: En el Fusionar Ordenar algorisme, el Divideix i conquereix estratègia s'utilitza per ordenar una llista d'elements. La imatge següent il·lustra els estats de divisió i fusió per ordenar la matriu utilitzant Fusionar Ordenar .



paraula clau final en java

Taula de contingut

diana mary blacker

Què és l'algoritme Divide and Conquer?

Divide and Conquer és una tècnica de resolució de problemes que consisteix a dividir un problema més gran en subproblemes, resoldre els subproblemes de manera independent i combinar les solucions d'aquests subproblemes per obtenir la solució del problema més gran.



Etapes de l'algoritme Divide and Conquer:

L'algoritme Divide and Conquer es pot dividir en tres etapes: Divideix , Conquerir i Fusionar .

1. Dividiu:

  • Desglosseu el problema original en subproblemes més petits.
  • Cada subproblema ha de representar una part del problema global.
  • L'objectiu és dividir el problema fins que no sigui possible més divisió.

2. Conquerir:

  • Resol cadascun dels subproblemes més petits individualment.
  • Si un subproblema és prou petit (sovint es coneix com el cas base), el resolem directament sense més recursivitat.
  • L'objectiu és trobar solucions per a aquests subproblemes de manera independent.

3. Fusionar:

  • Combina els subproblemes per obtenir la solució final de tot el problema.
  • Un cop resolts els subproblemes més petits, combinem recursivament les seves solucions per obtenir la solució del problema més gran.
  • L'objectiu és formular una solució per al problema original fusionant els resultats dels subproblemes.

Aplicacions de l'algoritme Divide and Conquer:

  • Ordenar per combinació: L'ordenació combinada és un exemple clàssic d'un algorisme d'ordenació dividir i conquerir. Desglossa la matriu en subarrays més petits, els ordena individualment i després els fusiona per obtenir la matriu ordenada.
  • Trobada mitjana: La mediana d'un conjunt de nombres es pot trobar utilitzant un enfocament de dividir i guanyar. En dividir recursivament el conjunt en subconjunts més petits, la mediana es pot determinar de manera eficient.
  • Mínima i màxima troballa: L'algorisme Divide and Conquer es pot utilitzar per trobar els elements mínims i màxims en una matriu simultàniament. En dividir la matriu en meitats i comparar els parells min-max de cada meitat, es poden identificar els mínims i màxims generals en complexitat de temps logarítmica.
  • Multiplicació matricial: L'algorisme de Strassen per a la multiplicació de matrius és una tècnica de dividir i conquerir que redueix el nombre de multiplicacions necessàries per a matrius grans desglossant les matrius en submatrius més petites i combinant els seus productes.
  • Problema del parell més proper: El problema de parelles més properes consisteix a trobar els dos punts més propers en un conjunt de punts en un espai multidimensional. Un algorisme de dividir i conquerir, com ara l'algorisme del parell més proper de dividir i conquerir, pot resoldre de manera eficient aquest problema dividint recursivament els punts i fusionant les solucions dels subproblemes.

Conceptes bàsics de l'algoritme Divide and Conquer:

Algoritmes estàndard activats Algoritme Divideix i Conquista :

Problemes basats en cerca binària:

  • Trobeu un element pic en una matriu donada
  • Comproveu l'element majoritari en una matriu ordenada
  • Element K-è de dues matrius ordenades
  • Troba el nombre de zeros
  • Trobeu el recompte de rotació a la matriu ordenada girada
  • Trobeu el punt on una funció creixent monòtonament esdevé positiva per primera vegada
  • Mediana de dues matrius ordenades
  • Mediana de dues matrius ordenades de diferents mides
  • El problema de la partició del pintor mitjançant la cerca binària

Practica problemes Algoritme Divideix i Conquista :

  • Arrel quadrada d'un nombre enter
  • Màxim i mínim d'una matriu utilitzant el nombre mínim de comparacions
  • Trobeu la freqüència de cada element en una matriu de rang limitat en menys de temps O(n).
  • Problema de rajoles
  • Recompte d'inversions
  • El problema de l'horitzó
  • Cerca en una matriu 2D ordenada per files i columnes
  • Assigna un nombre mínim de pàgines
  • Exponenciació modular (potència en aritmètica modular)

Links ràpids :

  • Apreneu l'estructura de dades i els algorismes | Tutorial DSA
  • 'Practica problemes' a Divide and Conquer
  • ‘Quizzes’ sobre Divide and Conquer