Teoria della complessità computazionale: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Bot: Sostituzione automatica (-{{sectstub}} +{{S sezione}}) |
|||
Riga 5:
==Misurazione delle risorse==
{{vedi anche|Stima asintotica}}
Per misurare le risorse computazionali richieste dalla soluzione di un problema, bisogna fare riferimento ad un modello di calcolo che sia il più possibile generico, in modo che i risultati ottenuti siano riproducibili anche su altri modelli di calcolo: la [[macchina di Turing]] soddisfa questo requisito. Infatti si dimostra che qualunque modello di calcolo scelto (come ad esempio la [[macchina RAM]], ma si può parlare anche di [[computer]] reali), ai fini della classificazione dei problemi, si comporta come la macchina di Turing.
Per quel che riguarda la misurazione della risorsa '''tempo''', data una macchina di Turing <math>M</math>, si dice che '''<math>M</math> opera in tempo <math>f(n)</math>''' se dato un input <math>x</math> di lunghezza <math>n</math>, la macchina <math>M</math> produce il risultato in <math>f(n)</math> passi.
| |||