Cos’è il metodo di sostituzione?
Il metodo di sostituzione è una delle principali tecniche per risolvere le ricorrenze, in particolare per dimostrare il valore
Passi del Metodo:
- Formulazione dell’Ipotesi: Si intuisce una forma asintotica per la soluzione
, ad esempio , o . L’intuizione può derivare da casi simili o dall’analisi dell’albero di ricorsione. - Caso Base: Si verifica che l’ipotesi sia valida per il caso base della ricorrenza (per
sufficientemente piccolo, spesso ). - Passo Induttivo: Assumendo che l’ipotesi sia vera per tutti i valori
(ipotesi induttiva), si deve dimostrare che vale anche per . - Per
: Si assume per e si cerca di mostrare per una costante opportuna e per . - Per
: Si assume per e si cerca di mostrare .
- Per
Esempio di metodo di sostituzione con Merge Sort
L’algoritmo Merge sort è un classico esempio di Divide et impera.
- DIVIDE: Il problema viene suddiviso in 2 sottoproblemi di dimensione
in tempo costante ( ). - IMPERA: I 2 sottoproblemi vengono risolti ricorsivamente, contribuendo con
al costo totale. - COMBINA: Le soluzioni dei sottoproblemi vengono fuse in tempo
. La ricorrenza per MergeSort è
. Dimostrazione
per MergeSort:>
- Ipotesi Induttiva:
per qualche costante e per . - Passo Induttivo: Sostituiamo l’ipotesi nella ricorrenza:
Affinché
, dobbiamo garantire che . Questo è possibile scegliendo una costante sufficientemente grande in modo che . Ad esempio, se è bounded by , allora , cioè . Così, , e quindi .
Errori comuni e soluzioni
Un errore comune si verifica quando i termini di ordine inferiore non sono gestiti correttamente.
- Problema: sia la ricorrenza
. Se ipotizziamo e tentiamo di dimostrare : Questo non è sufficiente per concludere , poiché non è necessariamente minore o uguale a per ogni se la costante è positiva. La costante potrebbe essere grande abbastanza da invalidare la disuguaglianza per piccoli . - Soluzione (sottrazione di un termine di ordine inferiore): per risolvere questo, si aggiunge un termine di ordine inferiore all’ipotesi induttiva, come
per qualche costante . Scegliamo come una costante . Vogliamo . Questo si semplifica a . Scegliendo sufficientemente grande (es. ), la disuguaglianza vale per . Questo porta a .