logo

TechCodeview

Algoritmo 'dividi e conquista'.

Algoritmo Dividi e Impera è una strategia di problem solving che prevede la scomposizione di un problema complesso in parti più piccole e più gestibili, risolvendo ciascuna parte individualmente e quindi combinando le soluzioni per risolvere il problema originale. È una tecnica algoritmica ampiamente utilizzata in informatica e matematica.

Esempio: Nel Unisci ordinamento algoritmo, il Dividere e conquistare La strategia viene utilizzata per ordinare un elenco di elementi. L'immagine sotto illustra gli stati di divisione e unione per ordinare l'array utilizzando Unisci ordinamento .



Tabella dei contenuti

Che cos'è l'algoritmo 'Dividi e conquista'?

Divide and Conquer è una tecnica di problem solving che prevede la suddivisione di un problema più grande in sottoproblemi, risolvendo i sottoproblemi in modo indipendente e combinando le soluzioni di tali sottoproblemi per ottenere la soluzione del problema più grande.



Fasi dell'algoritmo “dividi e conquista”:

L’algoritmo “Dividi e conquista” può essere suddiviso in tre fasi: Dividere , Conquistare E Unisci .

1. Dividi:

  • Suddividere il problema originale in sottoproblemi più piccoli.
  • Ogni sottoproblema dovrebbe rappresentare una parte del problema complessivo.
  • L’obiettivo è dividere il problema finché non sia più possibile alcuna ulteriore divisione.

2. Conquista:

  • Risolvi individualmente ciascuno dei sottoproblemi più piccoli.
  • Se un sottoproblema è sufficientemente piccolo (spesso indicato come caso base), lo risolviamo direttamente senza ulteriore ricorsione.
  • L'obiettivo è trovare soluzioni per questi sottoproblemi in modo indipendente.

3. Unisci:

  • Combina i sottoproblemi per ottenere la soluzione finale dell'intero problema.
  • Una volta risolti i sottoproblemi più piccoli, combiniamo ricorsivamente le loro soluzioni per ottenere la soluzione del problema più grande.
  • L'obiettivo è formulare una soluzione per il problema originale unendo i risultati dei sottoproblemi.

Applicazioni dell'algoritmo Dividi e Impera:

  • Unisci ordinamento: Merge sort è un classico esempio di algoritmo di ordinamento divide et impera. Suddivide l'array in sottoarray più piccoli, li ordina individualmente e quindi li unisce per ottenere l'array ordinato.
  • Risultato mediano: La mediana di un insieme di numeri può essere trovata utilizzando un approccio divide et impera. Dividendo ricorsivamente l'insieme in sottoinsiemi più piccoli, la mediana può essere determinata in modo efficiente.
  • Risultati Min e Max: L'algoritmo Divide and Conquer può essere utilizzato per trovare contemporaneamente sia gli elementi minimi che quelli massimi in un array. Dividendo l'array a metà e confrontando le coppie min-max di ciascuna metà, è possibile identificare il minimo e il massimo complessivi in ​​termini di complessità temporale logaritmica.
  • Moltiplicazione di matrici: L’algoritmo di Strassen per la moltiplicazione delle matrici è una tecnica “divide et impera” che riduce il numero di moltiplicazioni richieste per matrici di grandi dimensioni suddividendo le matrici in sottomatrici più piccole e combinando i loro prodotti.
  • Problema della coppia più vicina: Il problema della coppia più vicina consiste nel trovare i due punti più vicini in un insieme di punti in uno spazio multidimensionale. Un algoritmo divide et impera, come l'algoritmo divide et impera della coppia più vicina, può risolvere in modo efficiente questo problema dividendo ricorsivamente i punti e unendo le soluzioni dei sottoproblemi.

Nozioni di base sull'algoritmo “dividi e conquista”:

Algoritmi standard attivi Algoritmo 'dividi e conquista'. :

Problemi basati sulla ricerca binaria:

  • Trova un elemento di picco in un dato array
  • Controlla l'elemento di maggioranza in un array ordinato
  • Elemento K-esimo di due array ordinati
  • Trova il numero di zeri
  • Trova il conteggio delle rotazioni nell'array ordinato ruotato
  • Trova il punto in cui una funzione monotonicamente crescente diventa positiva la prima volta
  • Mediana di due array ordinati
  • Mediana di due array ordinati di dimensioni diverse
  • Il problema della partizione del pittore utilizzando la ricerca binaria

Esercitati sui problemi Algoritmo 'dividi e conquista'. :

  • Radice quadrata di un numero intero
  • Massimo e minimo di un array che utilizza il numero minimo di confronti
  • Trova la frequenza di ciascun elemento in un array con intervallo limitato in un tempo inferiore a O(n).
  • Problema di piastrellatura
  • Contare le inversioni
  • Il problema dell'orizzonte
  • Cerca in una matrice 2D ordinata per riga e per colonna
  • Assegnare il numero minimo di pagine
  • Esponenziazione modulare (potenza nell'aritmetica modulare)

Link veloci :

  • Impara la struttura dei dati e gli algoritmi | Tutorial DSA
  • “Problemi pratici” su Divide and Conquer
  • “Quiz” su Dividi e Impera