確定型空間複雜性測度

確定型空lei複雜性測度(deterministic spacecomplexity measure)一種複雜性測度.它是以所需空間為度量的一種複雜性測度.設M為(確定型)算法，若對M輸人字W後，計算收斂，並且在整個計算過程使用了n個空間單元(如紙帶單元)，則稱n為M在輸人W的計算空間.如果計算不收斂，則其計算空間無定義.若以}M (W)表示M在輸人W時的計算空間，並以}M作為M的複雜性測度，則稱}M為空間複雜性測度，若Mo,M…為某種算法的枚舉，並以中表示從之空間複雜性測度}M，則- }}i}iE。稱為關於這種算法的空間複雜性測度確定型).空間複雜性用DSP}ICE表示.設}M為算法M的空間複雜性測度，則函式}'M<n)=max{}M<W) }W字長為n}稱為M的工作空間(函式)或稱為M的空間複雜性函式.