英文
deterministic space complexity measure
简介
一种复杂性测度.它是以所需空间为度量的一种复杂性测度.设M为(确定型)算法，若对M输入字W后，计算收敛，并且在整个计算过程使用了n个空间单元(如纸带单元)，则称n为M在输入W的计算空间.如果计算不收敛，则其计算空间无定义.若以ΦM(W)表示M在输入W时的计算空间，并以ΦM作为M的复杂性测度，则称ΦM为空间复杂性测度，若M0，M1，…为某种算法的枚举，并以Φi表示Mi之空间复杂性测度ΦMi，则Φ={Φi}i∈ω称为关于这种算法的空间复杂性测度(确定型).空间复杂性用DSPACE表示.设ΦM为算法M的空间复杂性测度，则函数
Φ′M(n)=max{ΦM(W)|W字长为n}
称为M的工作空间(函数)或称为M的空间复杂性函数.