Back DTIME German DTIME English DTIME Spanish DTIME French DTIME Japanese DTIME Dutch DTIME Polish Dtime Portuguese DTIME Serbian DTIME Vietnamese
En la Teoria de complexitat computacional, la família DTIME (de vegades simplement TIME) és el recurs de computació en temps de computació per una màquina de Turing determinista. Representa la quantitat de temps (o nombre de cicles de computació) que un computador "normal" prendrà per resoldre un cert problema computacional usant un cert algorisme. És un dels recursos més ben estudiats perquè es correspon amb un recurs real força important com és el temps de còmput.[1][2]
Aquest recurs s'utilitza per definir classes de complexitat, conjunts de problemes de decisió que es poden resoldre usant un cert temps de computació. Si un problema amb una entrada de mida n es pot solucionar en O(f(n)), es te la classe de complexitat DTIME(f(n)). No hi ha restricció en la quantitat de memòria utilitzada, però pot haver-hi restriccions en d'altres recursos.
- ↑ Computational complexity theory. Providence, R.I.: American Mathematical Society, 2004. ISBN 082182872X.
- ↑ «Complexity Zoo:D - Complexity Zoo» (en anglès). Arxivat de l'original el 2018-12-02. [Consulta: 2 desembre 2018].