[Algoritmi] Algoritmo sul quoziente ed efficienza
Salve a tutti!
Sto scrivendo la tesina per l'esame di maturità e sto affrontando l'argomento degli algoritmi ma ho un dubbio.
Nello studiare la questione sull'efficienza di un algoritmo mi sono imbattuto in questa presentazione:
http://www.di.unito.it/~damiani/DIDATTI ... cienza.pdf
Alle pagine 3-4-5-6 vengono mostrati due diversi algoritmi per il calcolo del quoziente di due numeri, per far capire che, pur avendo lo stesso risultato, non hanno la stessa complessità. Il problema è che non riesco proprio a capire quale metodo venga usato nel secondo algoritmo. Qualcuno potrebbe spiegarmelo?
Grazie mille in anticipo a tutti!
Sto scrivendo la tesina per l'esame di maturità e sto affrontando l'argomento degli algoritmi ma ho un dubbio.
Nello studiare la questione sull'efficienza di un algoritmo mi sono imbattuto in questa presentazione:
http://www.di.unito.it/~damiani/DIDATTI ... cienza.pdf
Alle pagine 3-4-5-6 vengono mostrati due diversi algoritmi per il calcolo del quoziente di due numeri, per far capire che, pur avendo lo stesso risultato, non hanno la stessa complessità. Il problema è che non riesco proprio a capire quale metodo venga usato nel secondo algoritmo. Qualcuno potrebbe spiegarmelo?
Grazie mille in anticipo a tutti!
Risposte
Non si capisce dalle slide, ma suppongo che intenda dire di partire dal numero \(m\) e continuare a sottrarre \(n\) fino a quando non si arrivi ad un numero minore di \(n\). Contando il numero di sottrazioni si ha il quoziente intero (la ragione per cui penso sia questo algoritmo è che nella pagina successiva dice che per fare quel calcolo sono necessarie tutte quelle sottrazioni e quel numero è il quoziente). Ma sinceramente è un pessimo esempio. In effetti la divisione intera è una operazione che un computer ha già implementata al suo interno per cui a meno di lavorare a livello di hardware non capiterà mai di fare qualcosa di simile.