“Divide et impera” in strutture dati
La famosa frase latina “Divide et impera” nel contesto dell’informatica e delle strutture dati, indica una metodologia di progettazione che permette di formulare algoritmi asintoticamenteefficienti.
Si basa su 3 fasi principali (caso ricorsivo):
- Divide: il problema viene suddiviso in uno o più sotto-problemi più semplici.
- Impera: i sotto-problemi vengono risolti ricorsivamente
- Combina: le soluzioni dei sotto-problemi vengono combinate per formare la soluzione di un problema.
La ricorsione si arresta quando si arriva ad un problema abbastanza piccolo (caso base) da poter essere risolto in modo semplice.