|
|
La tecnica di Divide et Impera utilizzata per la progettazione di algoritmi consiste in:
Partizionare il problema in sottoproblemi più piccoli dello stesso tipo;
Risolvere i sottoproblemi;
Ricombinare le soluzioni parziali per ottenere la soluzione del problema originale.
La complessità per risolvere un problema con la tecnica di Divide et Impera corrisponde a:
dove:
c: costante
D(n): numero di operazioni per dividere problema
C(n): numero di operazioni per combinare risultati
Per esempio l ’algoritmo di ricerca binaria rientra nella classe di algoritmi di tipo Divide Et Impera.
La chiamata ricorsiva avviene infatti solo su uno dei due sottoproblemi. L’efficienza della tecnica dipende dalla dimensione dei sottoproblemi. Osservando la relazione di ricorrenza, il bilanciamento della dimensione dei sottoproblemi risulta la chiave di volta per ottenere algoritmi efficienti. Di seguito due algoritmi creati con la tecnica Divide et Impera:
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.