此条目没有列出任何参考或来源。 (2011年4月15日) 维基百科所有的内容都应该可供查证。请协助补充可靠来源以改善这篇条目。无法查证的内容可能会因为异议提出而移除。 |
在复杂度理论内,DLOGTIME是一个复杂度类,其问题可以用决定型图灵机,在对数成长的时间内解决。这是使用决定型时间,所能定义出最小且非单纯(non-trivial)的复杂度类。这类复杂度一定使用随机存取图灵机来定义,因为机器没有足够的时间来读取整个输入(输入的大小,成长率是O(n))。
DLOGTIME-均一性(uniformity)在电路复杂性里面是很重要的。
询问输入字串的长度这个问题属于DLOGTIME,因为我们可以对可能的输入大小进行折半搜索算法(binary search)。