跳转到内容

DLOGTIME

维基百科,自由的百科全书

复杂度理论内,DLOGTIME是一个复杂度类,其问题可以用决定型图灵机,在对数成长的时间内解决。这是使用决定型时间,所能定义出最小且非单纯(non-trivial)的复杂度类。这类复杂度一定使用随机存取图灵机来定义,因为机器没有足够的时间来读取整个输入(输入的大小,成长率是O(n))。

DLOGTIME-均一性(uniformity)在电路复杂性里面是很重要的。

询问输入字串的长度这个问题属于DLOGTIME,因为我们可以对可能的输入大小进行折半搜索演算法(binary search)。