计算资源(resource on the computation)
计算复杂性理论的一个术语.
指计算中所需的各种资源一般地,各种计算模型的主要资源有并行时间、串行时间和空间三种.
1.并行时间和巡回.并行时间一般指并行模型计算时所需步数,例如,向量机的自始至终执行指令的总条数.但对串行模型也可以定义一种称为巡回的资源.可以证明它相当于并行时间.对于多带图灵机,它是工作带头部改变方向的次数.一般地,巡回是周相的总数,而周相则是串行模型工作中的一个阶段,在此阶段中计算出来而记录在工作空间上的信息,不再被读到.
2.串行时间.计算过程中原始运算的总量.对于串行模型而言,它代表计算自始至终的总步数;对于并行模型而言,每一步可以同时作许多个原始的运算,自始至终各步的原始运算数目的总和就是串行时间.
3.空间.在计算过程中需要记录下来以备后用的最大中间信息量.对于多带图灵机,是计算过程中用过的工作带上的方格数.