So che spesso si utilizza l'induzione (quindi un caso base e il passo induttivo) e le inferenza da ciclo.
Un esempio di esercizio:
Dati un albero binario di ricerca T (contenente valori interi distinti) e due valori interi min, max, con min < max, scrivere un algoritmo occurrences(TREE T, integer min, integer max) che restituisca il numero di valori di T che sono compresi fra min e max, estremi inclusi. Discutere correttezza e complessità della soluzione proposta.
L'algoritmo che ho scritto in pseudocodice è :
- Codice:
int occurrences(TREE node, integer min, integer max){
if(node == NULL)
return 0
else if(node.key < min)
return occurrences(node.right, min, max)
else if(node.key > max)
return occurrences(node.left, min, max)
else
return 1 + occurrences(node.left, min, max) + occurrences(node.right, min, max)
}
La complessità è O(n) perchè deve dovrebbe scandire tutti i nodi dell'albero, ma in realtà scarta i sottoalberi in cui sicuramente non c'è un elemento cercato.
Nella correttezza invece iniziano i dolori: decido di fare un'induzione sul numero di chiamate ricorsive (h).
Devo dimostrare che la funzione, dato un albero BST corretto, ritorna in ogni caso il numero di nodi la cui chiave è compresa fra min e max.
Base: 0 chiamate ricorsive -> l'albero è vuoto -> ritorno 0 ed è corretto;
Ipotesi induttiva: con h-1 chiamate ricorsive l'algoritmo è corretto(?);
Passo: dimostrare che con h chiamate ricorsive, in cui h è l'ultima chiamata prima della terminazione della funzione, l'algoritmo soddisfa le premesse. Ma come?
Grazie.