Teoria della complessità computazionale: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
m Annullate le modifiche di 217.57.67.234 (discussione), riportata alla versione precedente di LauBot Etichetta: Rollback |
||
Riga 11:
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 ''<math>f(n)</math>'' è il ''massimo'' numero di passi necessari alla macchina per produrre il risultato su un input <math>x</math> di lunghezza <math>n</math>.
Per quel che riguarda la
Affinché queste affermazioni siano valide, <math>f(n)</math> dev'essere una ''funzione di complessità propria'', cioè deve soddisfare le seguenti condizioni:
| |||